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); PRintf("%d ",ans); for (int i = 1; i <= n; i++) if (map.a[i][i] > sum) sum = map.a[i][i]; printf("%d/n",sum);}

上一篇：spark创建DataFrames

下一篇：Udacity Linux 命令行基础 Shell 入门

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注