JZOJ 3640. 【COCI2014】utrka

2019-11-06 06:27:37

字體：大中小

來源：轉載

供稿：網友

Description

這里寫圖片描述

Input

這里寫圖片描述

Output

這里寫圖片描述

Sample Input

輸入1：

3 4

1 2 3 0

2 3 3 0

3 1 0 100

2 1 0 4

輸入2：

5 7

1 2 4 1

2 3 5 1

3 1 1 6

1 3 15 5

2 4 7 5

4 5 1 4

5 3 1 0

Sample Output

輸出1：

2 1

輸出2：

5 2

Data Constraint

2<=N<=300,2<=M<=N*(N-1)

分析

我們用f[k][i][j]表示從i到j共經過k個節點的最大權值，之后二分一下答案就好

代碼

#include <bits/stdc++.h>#define N 305#define INF -0x3f3f3f3fstruct NOTE{ int a[N][N];};NOTE f[15];NOTE map;int mid,sum,ans;int n,m;void merge(NOTE &a,NOTE b,NOTE c){ for (int s = 1; s <= n; s++) for (int i = 1; i <= n; i++) if (b.a[i][s] > INF) for (int j = 1; j <= n; j++) if (c.a[s][j] > INF) if (b.a[i][s] + c.a[s][j] > a.a[i][j]) a.a[i][j] = b.a[i][s] + c.a[s][j];}bool cheak(){ for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (map.a[i][j] + f[mid].a[j][i] > 0) return true; return false;}int main(){// freopen("utrka.in","r",stdin);// freopen("utrka.out","w",stdout); int k; scanf("%d%d",&n,&m); for (k = 0; k < 15; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[k].a[i][j] = INF; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) map.a[i][j] = INF; for (int i = 1; i <= m; i++) { int x,y,tm,ts; scanf("%d%d%d%d",&x,&y,&tm,&ts); f[0].a[x][y] = ts - tm; } for (int i = 1; i <= n; i++) map.a[i][i] = 0, f[0].a[i][i] = 0; for (k = 1; k < 15; k++) { f[k] = f[k - 1]; merge(f[k],f[k - 1],f[k - 1]); for (int i = 1; i <= n; i++) if (f[k].a[i][i] > 0) break; if ((1 << k) > n) break; } mid = k; ans = 0; while (mid >= 0) { if (!cheak()) { merge(map,map,f[mid]); ans += (1 << mid); } mid --; } int r = 0; int l = k; while (r != l) { mid = (l + r) >> 1; if (cheak()) { l = mid; } else r = mid + 1; } merge(map,map,f[r]); ans += (1 << r);