#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cstring>
#define go(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,x) for(int i=a[x];i>-1;i=e[i].next)
#define In() freopen("in.in","r",stdin)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;const int N=5000;
struct E{int v,next,flow,cap;}e[N*N];
int n,n_power,n_user,m,S,T,head[N],k=0,d[N];
int num[N],cur[N],preE[N],preN[N];
void ADD(int u,int v,int flow,int cap){e[k]=(E){v,head[u],flow,cap};head[u]=k++;}
void BFS(){queue<int>q;bool vis[N]={0};q.push(T);d[T]=0;while(!q.empty())
{int u=q.front();q.pop();fo(i,head,u){int v=e[i].v;
if(!e[i].cap&&!vis[v])vis[v]=1,d[v]=d[u]+1,q.push(v);}}
}
int aug(){int u,a=2147483645;
u=T;while(u!=S){int i=preE[u];a=min(a,e[i].cap-e[i].flow);u=preN[u];}
u=T;while(u!=S){int i=preE[u];e[i].flow+=a;e[i^1].flow-=a;u=preN[u];}
return a;}
int main(){while(~scanf("%d%d%d%d",&n,&n_power,&n_user,&m)){	
S=0;T=n+1;char _;mem(head,-1);
go(i,1,m){int u,v,cap;scanf(" %c%d%c%d%c%d",&_,&u,&_,&v,&_,&cap);
u++,v++;ADD(u,v,0,cap);ADD(v,u,0,0);}
go(i,1,n_power){int v,cap;scanf(" %c%d%c%d",&_,&v,&_,&cap);
v++;ADD(S,v,0,cap);ADD(v,S,0,0);}
go(i,1,n_user){int u,cap;scanf(" %c%d%c%d",&_,&u,&_,&cap);
——u++;ADD(u,T,0,cap);ADD(T,u,0,0);}BFS();mem(num,0);
——go(i,0,n+1)num[d[i]]++,cur[i]=head[i];int u=S,flow=0;
——while(d[S]<T+1){u==T?flow+=aug(),u=S:1;
——bool retreat=1;fo(i,cur,u){int v=e[i].v;if(e[i].cap>e[i].flow&&d[u]==d[v]+1)
——{retreat=0;cur[u]=preE[v]=i;preN[v]=u;u=v;break;}}
——if(!retreat)continue;int Min=T;
——fo(i,head,u){int v=e[i].v;if(e[i].cap>e[i].flow)Min=min(Min,d[v]);}
——if(!(--num[d[u]]))break;num[d[u]=Min+1]++;cur[u]=head[u];u==S?1:u=preN[u];
——}printf("%d\n",flow);}return 0;
}//Paul_Guderian

• Re:【ISAP63ms,那么0ms是怎么搞出来的？而且代码还很短】 (1858) SorrowBecase 2017-04-30 10:48:12
  • Re:【ISAP63ms,那么0ms是怎么搞出来的？而且代码还很短】 (18) SorrowBecase 2017-04-30 10:48:57