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

## 0_0 这题很奇怪么？ sscanf 啊。1A。

Posted by dongshimou at 2014-07-25 15:03:14 on Problem 1459
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
#define LL long long
#define acfun std::ios::sync_with_stdio(false)
using namespace std;

int n,np,nc,m;
struct lx
{
int c,f;
};
lx g[301][301];
bool vis[301];
int path[301];
int flow[301];

void EK(int start,int thend)
{
int maxflow=0;
while(1)
{
for(int i=0;i<n+2;i++)
vis[i]=0,path[i]=-1,flow[i]=0;
queue<int>q;
q.push(start);
vis[start]=1,flow[start]=INF;
while(!q.empty()&&!vis[thend])
{
int u=q.front();q.pop();
for(int j=0;j<n+2;j++)
{
if(vis[j])continue;
if(g[u][j].f<g[u][j].c)
{
vis[j]=1;
path[j]=u;
flow[j]=min(flow[u],g[u][j].c-g[u][j].f);
q.push(j);

}
else if(g[j][u].f>0)
{
vis[j]=1;
path[j]=u;
flow[j]=min(flow[u],g[j][u].f);
q.push(j);
}
}
}
if(!vis[thend]||flow[thend]==0)break;

int v=thend,u=path[thend];
int tmp=flow[thend];

maxflow+=tmp;

while(u!=-1)
{
if(g[u][v].f<g[u][v].c)
g[u][v].f+=tmp;
else
g[v][u].f-=tmp;
v=u,u=path[v];

}
}
printf("%d\n",maxflow);
}

int main()
{
while(scanf("%d%d%d%d",&n,&np,&nc,&m)!=EOF)
{
for(int i=0;i<n+2;i++)
for(int j=0;j<n+2;j++)
g[i][j].c=g[i][j].f=0;
int u,v,c;
char str[1001];
while(m--)
{
scanf("%s",str);
sscanf(str,"(%d,%d)%d",&u,&v,&c);
g[u][v].c=c;

}
for(int i=0;i<np;i++)
{
scanf("%s",str);
sscanf(str,"(%d)%d",&v,&c);
g[n][v].c=c;
}
for(int i=0;i<nc;i++)
{
scanf("%s",str);
sscanf(str,"(%d)%d",&u,&c);
g[u][n+1].c=c;
}
EK(n,n+1);
}
}

Followed by: