[困]坑点：无向边，每条边只能走一次，但正向走一次后反向还能走一次，所以每次输入要建四条边。
#include#include #include #include #include using namespace std;int n,m,cnt;int head[50500],vis[50500],pre[50500];long long dis[50500];struct edge{ int u,v,w,cap,next;}e[50050<<2];void Initial(){ memset(head,-1,sizeof(head));}bool SPFA(){ memset(pre,-1,sizeof(pre)); for(int i=0;i<=n+2;i++){ dis[i]=1e11; } memset(vis,0,sizeof(vis)); queue que; vis[0]=1; que.push(0); dis[0]=0; while(!que.empty()){ int d=que.front(); que.pop(); vis[d]=0; for(int i=head[d];i!=-1;i=e[i].next){ int v=e[i].v; if(dis[v]>dis[d]+e[i].w && e[i].cap){ dis[v]=dis[d]+e[i].w; pre[v]=i; if(!vis[v]){ vis[v]=1; que.push(v); } } } } if(dis[n+1]<1e11){ return true; } return false;}int MCMF(){ int flow=0,mincost=0; while(SPFA()){ long long Minflow=1e11; int d=n+1; for(int i=pre[d];i!=-1;i=pre[e[i].u]){ Minflow=min(Minflow,(long long)e[i].cap); } flow+=Minflow; for(int i=pre[d];i!=-1;i=pre[e[i].u]){ e[i].cap-=Minflow; e[i^1].cap+=Minflow; } mincost+=dis[d]; } return mincost;}void add(int u,int v, int cap,int w){ e[cnt].u=u; e[cnt].v=v; e[cnt].w=w; e[cnt].cap=cap; e[cnt].next=head[e[cnt].u]; head[u]=cnt++; e[cnt].v=u; e[cnt].u=v; e[cnt].w=-1*w; e[cnt].cap=0; e[cnt].next=head[e[cnt].u]; head[v]=cnt++;}int main(){ while(~scanf("%d%d",&n,&m)){ cnt=0; Initial(); for(int i=0;i