Ikki's Story I - Road Reconstruction
| Time Limit: 2000MS | Memory Limit: 131072K |
| Total Submissions: 7546 | Accepted: 2185 |
Description
Ikki is the king of a small country – Phoenix, Phoenix is so small that there is only one city that is responsible for the production of daily goods, and uses the road network to transport the goods to the capital. Ikki finds that the biggest problem in the country is that transportation speed is too slow.
Since Ikki was an ACM/ICPC contestant before, he realized that this, indeed, is a maximum flow problem. He coded a maximum flow program and found the answer. Not satisfied with the current status of the transportation speed, he wants to increase the transportation ability of the nation. The method is relatively simple, Ikki will reconstruct some roads in this transportation network, to make those roads afford higher capacity in transportation. But unfortunately, the country of Phoenix is not so rich in GDP that there is only enough money to rebuild one road. Ikki wants to find such roads that if reconstructed, the total capacity of transportation will increase.
He thought this problem for a loooong time but cannot get it. So he gave this problem to frkstyc, who put it in this POJ Monthly contest for you to solve. Can you solve it for Ikki?
Input
The input contains exactly one test case.
The first line of the test case contains two integers N, M (N ≤ 500, M ≤ 5,000) which represents the number of cities and roads in the country, Phoenix, respectively.
M lines follow, each line contains three integers a, b, c, which means that there is a road from city a to city b with a transportation capacity of c (0 ≤ a, b < n, c ≤ 100). All the roads are directed.
Cities are numbered from 0 to n − 1, the city which can product goods is numbered 0, and the capital is numbered n − 1.
Output
You should output one line consisting of only one integer K, denoting that there are K roads, reconstructing each of which will increase the network transportation capacity.
Sample Input
2 1
0 1 1
Sample Output
1
Source
POJ Monthly--2007.03.04, Ikki
題目大意：
有n個點，m條有向邊，0号是生産站點，N-1是接受站點，每條邊都有限定的流量，Ikki知道這是一個最大流問題，他求出了其網絡的最大流，但是他發現這個網絡的最大流值很小，沒有運輸的效率，他想增加這個值，然而增加這個值的方法也很簡單，就是他需要對一些邊進行增加容量。然而政府比較窮，他隻能增加一條邊的容量，問有多少個這樣的邊。
思路：
1、首先分析，對于殘餘網絡中（不算退回邊），瓶頸邊的剩餘流量一定是0，也就是一條滿流邊、
2、那麼對于剩餘流量為0的邊，是不是加上容量就一定可行呢？
我們來看這樣一個例子：
明顯每條邊的剩餘流量都是0，而且我對其在原圖任意一條邊增加容量都不能達到使最大流值增加的情況。
3、那麼我們到底怎樣加才行呢？
我們再來看這樣一個例子
剩餘流量為：
顯然這種情況下，對這條剩餘流量為0的邊加流量，是一定會達到增加最大流值的目的的。
4、那麼我們仔細觀察上圖，不難了解：對于一條剩餘流量為0的邊，（在走流量大于0的邊的情況下）如果從源點能夠到達這條邊的from，并且這條邊的to能夠到達彙點。那麼這條邊就是一條可行邊。
5、那麼整體思路就是：跑一遍Dinic，得到殘餘網絡，對于每一條剩餘流量為0的邊，進行上述判斷，并記錄下可行邊數量即可。
Ac代碼：
#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
struct node
{
int from;
int to;
int next;
int w;
}e[50550];
int vis[5050];
int cur[5050];
int head[5050];
int divv[5050];
int n,m,cont,ss,tt;
void add(int from,int to,int w)
{
e[cont].from=from;
e[cont].to=to;
e[cont].w=w;
e[cont].next=head[from];
head[from]=cont++;
}
int makedivv()
{
memset(divv,0,sizeof(divv));
divv[ss]=1;
queue<int >s;
s.push(ss);
while(!s.empty())
{
int u=s.front();
if(u==tt)return 1;
s.pop();
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
int w=e[i].w;
if(w&&divv[v]==0)
{
divv[v]=divv[u]+1;
s.push(v);
}
}
}
return 0;
}
int Dfs(int u,int maxflow,int tt)
{
if(tt==u)return maxflow;
int ret=0;
for(int &i=cur[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
int w=e[i].w;
if(w&&divv[v]==divv[u]+1)
{
int f=Dfs(v,min(maxflow-ret,w),tt);
e[i].w-=f;
e[i^1].w+=f;
ret+=f;
if(ret==maxflow)return ret;
}
}
return ret;
}
void Dinic()
{
int ans=0;
while(makedivv()==1)
{
memcpy(cur,head,sizeof(head));
Dfs(ss,INF,tt);
ans++;
}
//printf("%d\n",ans);
}
int findd(int start,int end)
{
memset(vis,0,sizeof(vis));
queue<int >s;
s.push(start);
vis[start]=1;
while(!s.empty())
{
int u=s.front();
if(u==end)return 1;
s.pop();
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].to;
int w=e[i].w;
if(w)
{
if(vis[v]==0)
{
s.push(v);
vis[v]=1;
}
}
}
}
return 0;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
ss=1;
tt=n;
cont=0;
cont++;
cont--;
cont++;
cont--;
cont++;
cont--;
cont++;
cont--;
cont++;
cont--;//你打我啊~
memset(head,-1,sizeof(head));
for(int i=0;i<m;i++)
{
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
x++;y++;
add(x,y,w);
add(y,x,0);
}
Dinic();
int output=0;
for(int i=0;i<cont;i+=2)
{
if(e[i].w!=0)continue;
if(findd(ss,e[i].from)==1&&findd(e[i].to,tt)==1)output++;
}
printf("%d\n",output);
}
}
/*
4 6
0 1 4
0 2 2
1 2 2
1 3 1
2 3 7
2 0 1
*/