POJ 3204 最大流
題意：問加哪些邊容量增大能夠增加整體流量。
很顯然，增加單個邊容量改變全局容量，一遍最大流之後，這些邊只有可能出現在滿流的邊內，而且是一條路中唯一的一條滿流邊。
題解： 大眾解法，一遍最大流之後，整個圖跑殘了，記錄那些滿流的邊，從起點開始深搜，只走非滿流邊，從終點開始搜，只走非滿流邊，如果某條滿流邊起始點被起點標記，且終止點被終點標記，那麼這條滿流邊存在於有且僅有他自己的從起點到終點的非滿流路線中。這條邊為關鍵邊，Num++;
我的做法：既然一遍最大流之後 ，整個圖跑殘了，如果將某些關鍵邊進行添加流量操作，將會重新出現一條從起點到終點的通路，我們可以直接在殘余網絡中加流，然後進行從起點到終點的廣搜，如果可以到達 num ++,思路簡單，但是由於多次廣搜，如果用普通隊列實現dinic會超時，雖然用數組模擬隊列很不好，但是表示這樣確實很省時間。
代碼：
#include
#include
#include
#define INF 1000000000
#define N 1005
#define M 10005
using namespace std;
int tot, list[N], deep[N], n, m, q[2000005];
struct Node
{
int date, value, next, from;
}cun[2000005];
struct dian
{
int x, t;
}old,xin;
void add(int a, int b, int c)
{
cun[++tot].value = c;
cun[tot].date = b;
cun[tot].next = list[a];
cun[tot].from = a;
list[a] = tot;
cun[++tot].value = 0;
cun[tot].date = a;
cun[tot].next = list[b];
cun[tot].from = b;
list[b] = tot;
}
int BFS(int s,int t)
{
int i,x,v,tail=0,head=0;
memset(deep,255,sizeof(deep));
deep[s]=0;
q[tail++]=s;
while(head
{
x=q[head++];
for(i=list[x];i;i=cun[i].next)
{//printf("!\n");
if(cun[i].value&&deep[v=cun[i].date]==-1)
{
deep[v]=deep[x]+1;
if(v==t)
return 1;
q[tail++]=v;
}
}
}
return 0;
}
int mmin(int a,int b)
{
if(a
else return b;
}
int DFS(int s,int t,int min)
{
if(s==t) return min;
int neww=0;
for(int k=list[s];k;k=cun[k].next)
{
int c=cun[k].value;
int date=cun[k].date;
if(c==0||deep[date]!=deep[s]+1) continue;
int m=DFS(date,t,mmin(c,min-neww));
neww+=m;
cun[k].value-=m;
cun[k^1].value+=m;
if(neww==min) break;
}
if(neww==0) deep[s]=0;
return neww;
}
int dinic(int s,int t,int n)
{
int num=0;
while(BFS(s,t))
{
num+=DFS(s,t,INF);
}
return num;
}
void bulid()
{
int a, b, c;
for(int i = 0; i < m; i++ )
{
scanf("%d %d %d",&a, &b, &c);
add(a+1, b+1, c);
}
int k = dinic(1, n, n+5);
int num = 0;
for(int i = 2; i <= tot; i += 2)
{
if(!cun[i].value)
{
cun[i].value += 1;
if(BFS(1, n)) num++;
cun[i].value -= 1;
}
}
printf("%d\n",num);
}
int main()
{
while(scanf("%d%d",&n, &m)!=EOF)
{
memset(list,0,sizeof(list));
tot = 1;
bulid();
}
}
