Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 求救，TLE了，在discuss上一个差不多的模板过了

Posted by zl_leaf at 2012-04-19 13:55:50 on Problem 1459
```#include<stdio.h>
#include<string.h>
#include<iostream>
#include<memory.h>
#include<queue>
#include<cstdio>
#include <cmath>

using namespace std;

#define MAXN 110
#define INF 999999999
int n,np,nc,m;
int cap[MAXN][MAXN],father[MAXN],res;
int start,end;
queue<int>q;

void maxflow()
{
int x,i,temp,ok;

while(1)
{
ok=0;
for(i=0;i<=end;i++)
father[i]=-1;

q.push(start);
temp=INF;
while(!q.empty())
{
x=q.front();
q.pop();
for(i=0;i<=end;i++)
{
if(father[i]==-1&&cap[x][i]>0)
{
if(i==end)
ok=1;
father[i]=x;
temp=temp<cap[x][i]?temp:cap[x][i];

q.push(i);
}
}
}
if(!ok)  break;

for(i=end;i!=0;i=father[i])
{
cap[father[i]][i]-=temp;
cap[i][father[i]]+=temp;
}
res+=temp;
}
return ;
}

int main()
{
int i,j,a,b,c;
char s[30];
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
{
start=0;
end=n+1;
for(i=0;i<=end;i++)
for(j=0;j<=end;j++)
cap[i][j]=0;
for(i=0;i<m;i++)
{
scanf("%s",s);
sscanf(s,"(%d,%d)%d",&a,&b,&c);
cap[a+1][b+1]+=c;
}
for(i=0;i<np;i++)
{
scanf("%s",s);
sscanf(s,"(%d)%d",&a,&b);
cap[start][a+1]+=b;
}
for(i=0;i<nc;i++)
{
scanf("%s",s);
sscanf(s,"(%d)%d",&a,&b);
cap[a+1][end]+=b;
}
res=0;
maxflow();
printf("%d\n",res);
}
return 0;
}
```

Followed by:

User ID:
Title:

Content: