4773: 负环

4773: 负环

Time Limit: 100 Sec   Memory Limit: 256 MB Submit: 209   Solved: 105 [ Submit][ Status][ Discuss]

Description

在忘记考虑负环之后，黎瑟的算法又出错了。对于边带权的有向图 G = (V, E)，请找出一个点数最小的环，使得 环上的边权和为负数。保证图中不包含重边和自环。

Input

第1两个整数n, m,表示图的点数和边数。 接下来的m行，每<=三个整数ui, vi, wi，表<=有一条从ui到vi，权值为wi的有向边。 2 <= n <= 300 0 <= m <= n(n <= 1) 1 <= ui, vi <= n |wi| <= 10^4

Output

仅一行一个整数，表示点数最小的环上的点数，若图中不存在负环输出0。

Sample Input

3 6 1 2 -2 2 1 1 2 3 -10 3 2 10 3 1 -10 1 3 10

Sample Output

2

HINT

Source

[ Submit][ Status][ Discuss] 定义f[i][j][k]:从点i出发到点j，经过k条边的最短路长度 可以枚举k，然后用floyed算法暴力跑一跑，O(n^4)的优秀复杂度 #include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #define min(a,b) ((a) < (b) ? (a) : (b)) #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int N = 303; const int INF = 1E9 + 233; int n,m,cur,nex = 1,f[2][N][N],g[N][N]; void Floyed() { for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[nex][i][j] = min(f[nex][i][j],f[cur][i][k] + g[k][j]); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif cin >> n >> m; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) f[cur][i][j] = f[nex][i][j] = g[i][j] = INF; for (int i = 1; i <= n; i++) f[cur][i][i] = 0; while (m--) { int x,y,w; scanf("%d%d%d",&x,&y,&w); g[x][y] = w; } for (int i = 1; i <= n; i++,swap(cur,nex)) { Floyed(); for (int j = 1; j <= n; j++) if (f[nex][j][j] < 0) {cout << i << endl; return 0;} for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) f[cur][j][k] = INF; } cout << 0 << endl; return 0; }