# RQNOJ 306. 破坏石油运输系统问题

### Analyse :

（我之前想的方法一直是扫描每一条边是否饱和。。不过这个想法太暴力了。。因为会存在可以从其他地方绕过这条边而产生同样效果的路径。）

。。。Dinic 完以后，用 Floyd 求残量网络的传递闭包。

/*
ID: xiaodao
PROG: RQ 306. 破坏石油运输系统问题
TAGS: Network-Flow
*/

#include
#include
#include
using namespace std;
const int INF = 1000000;
const int N = 131, M = N*(N-1)/2;
struct edge{
int x, y;
};
struct rec{
int v, p, k;
}; // Stack type
int C[N][N]; // Residual graph ..
int L[N]; edge E[M]; // Leval label ... Edge content.
int n, m, s, t;

void bfs(){
memset(L, -1, sizeof(L));

head = 0; tail = 1; Q[0]  = 1;
L[1] = 0;

int u, v;
L[u] = -1;
top--;
}
else{
cache[u] = v+1; top++;
stack[top].v = v;
if (C[u][v]  < stack[top-1].k){
stack[top].k = C[u][v];
stack[top].p = top-1;
}
else{
stack[top].k = stack[top-1].k;
stack[top].p = stack[top-1].p;
}
}
}
bfs();
}
}

void solve(){
bool G[n+1][n+1];

for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
G[i][j] = (C[i][j] != 0);

for (int k=1;k<=n;k++)
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
G[i][j] = G[i][j] || (G[i][k] && G[k][j]);

vector list;
for (int i=1;i<=m;i++)
if (!G[E[i].x][E[i].y] || !G[E[i].y][E[i].x]) list.push_back(i);

cout << list.size() << endl;
for (int i=0;i> n >> m >> s >> t;
for (int i=1;i<=m;i++){
scanf("%d%d%d", &E[i].x, &E[i].y, &c);
r(E[i].x); r(E[i].y);
C[E[i].x][E[i].y] += c;
C[E[i].y][E[i].x] += c;
}
}

int main(){
init(); dinic();
solve();
}