poj 1459 Power Network(最大流)

題意：
給幾個發電站，給幾個消耗站，再給幾個轉發點。
發電站只發電，消耗站只消耗電，轉發點只是轉發電，再給各個傳送線的傳電能力。
問你消耗站能獲得的最多電是多少。

思路：

增加一個超級源點，和超級匯點。。把所給的發電站都和超級源點相連，把所給的消耗戰都和超級匯點相連。。

這題還要注意的就是輸入格式了！

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
#define inf 10000000
#define min(a,b) a<b?a:b


int map[210][210],maxf[210],pre[210];
int n,m,nc,np; 


int bfs()
{
int i;
queue<int>q;
for(i=0;i<=n+1;i++)
{
maxf[i]=inf;
pre[i]=-1;
}
pre[0]=0;
q.push(0);
while(!q.empty())
{
int qian=q.front();
q.pop();
int hou;
for(hou=1;hou<=n+1;hou++)
{
if(map[qian][hou]&&pre[hou]==-1)
{
pre[hou]=qian;
maxf[hou]=min(maxf[qian],map[qian][hou]);
q.push(hou);
}
}
}
if(pre[n+1]==-1)return 0;
return maxf[n+1];
}


int ek()
{
int max=0,kejia;
while(kejia=bfs())
{
max+=kejia;
int index=n+1,qian;
while(index!=0)
{
qian=pre[index];
map[qian][index]-=kejia;
map[index][qian]+=kejia;
index=qian;
}
}
return max;
}


int main()
{
int i,ans,u,v,w;
char ch[10];
while(scanf("%d %d %d %d",&n,&nc,&np,&m)!=EOF)
{
memset(map,0,sizeof(map));
for(i=0;i<m;i++)
{
scanf("%s",ch);
sscanf(ch,"(%d,%d)%d",&u,&v,&w);
map[u+1][v+1]=w;
}
for(i=0;i<nc;i++)
{
scanf("%s",ch);
sscanf(ch,"(%d)%d",&u,&w);
map[0][u+1]=w;
}
for(i=0;i<np;i++)
{
scanf("%s",ch);
sscanf(ch,"(%d)%d",&v,&w);
map[v+1][n+1]=w;
}
ans=ek();
printf("%d\n",ans);
}
return 0;
}