首页 > 代码库 > POJ 3204 Ikki's Story I - Road Reconstruction 最大流关键边
POJ 3204 Ikki's Story I - Road Reconstruction 最大流关键边
题目大意:给出一个裸的最大流的图,求这个图中哪一条边的流量增大会使整个图的最大流增大。
前言:POJ400题达成~~~
思路:真心不知道这个题用预流推进怎么做,先给写预流推进的犇们点根蜡。。
我用的是Dinic,写起来就比较轻松。模拟一下Dinic的过程,加入一条边的流量增大就会使S到T的最大流增大的充要条件是
1.S->当前边的起始节点可以在残余网络中联通
2.当前边的终止节点->T可以在参与网络中联通
这样的话,增加了这条边的流量,就会有至少一的流量从S流到T,也就是增加了整个图的最大流。
然后检测的方法就是两次深搜。
CODE:
#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 20010 #define INF 0x3f3f3f3f #define S 0 #define T (points - 1) using namespace std; int points,edges; int head[MAX],total = 1; int next[MAX],aim[MAX],from[MAX],flow[MAX]; int deep[MAX]; bool vS[MAX],vT[MAX]; inline void Add(int x,int y,int f) { next[++total] = head[x]; aim[total] = y; flow[total] = f; from[total] = x; head[x] = total; } inline void Insert(int x,int y,int f) { Add(x,y,f); Add(y,x,0); } inline bool BFS() { static queue<int> q; while(!q.empty()) q.pop(); memset(deep,0,sizeof(deep)); deep[S] = 1; q.push(S); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = head[x]; i; i = next[i]) if(flow[i] && !deep[aim[i]]) { deep[aim[i]] = deep[x] + 1; q.push(aim[i]); if(aim[i] == T) return true; } } return false; } int Dinic(int x,int f) { if(x == T) return f; int temp = f; for(int i = head[x]; i; i = next[i]) if(deep[aim[i]] == deep[x] + 1 && flow[i] && temp) { int away = Dinic(aim[i],min(flow[i],temp)); if(!away) deep[aim[i]] = 0; flow[i] -= away; flow[i^1] += away; temp -= away; } return f - temp; } void DFS_S(int x) { vS[x] = true; for(int i = head[x]; i; i = next[i]) { if(vS[aim[i]]) continue; if(!(i&1) && flow[i]) DFS_S(aim[i]); } } void DFS_T(int x) { vT[x] = true; for(int i = head[x]; i; i = next[i]) { if(vT[aim[i]]) continue; if((i&1) && flow[i^1]) DFS_T(aim[i]); } } int main() { cin >> points >> edges; for(int x,y,z,i = 1; i <= edges; ++i) { scanf("%d%d%d",&x,&y,&z); Insert(x,y,z); } while(BFS()) Dinic(S,INF); DFS_S(S); DFS_T(T); int ans = 0; for(int i = 2; i <= total; i += 2) if(!flow[i] && vS[from[i]] && vT[aim[i]]) ++ans; cout << ans << endl; return 0; }
POJ 3204 Ikki's Story I - Road Reconstruction 最大流关键边
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。