1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #define V 10100 7 #define E 1000100 8 #define inf 99999999 9 using namespace std;10 int vis[V];11 int dist[V];12 int pre[V];13 14 struct Edge{15     int u,v,c,cost,next;16 }edge[E];17 int head[V],cnt;18 19 void init(){20     cnt=0;21     memset(head,-1,sizeof(head));22 }23 void addedge(int u,int v,int c,int cost)24 {25     edge[cnt].u=u;edge[cnt].v=v;edge[cnt].cost=cost;26     edge[cnt].c=c;edge[cnt].next=head[u];head[u]=cnt++;27 28     edge[cnt].u=v;edge[cnt].v=u;edge[cnt].cost=-cost;29     edge[cnt].c=0;edge[cnt].next=head[v];head[v]=cnt++;30 }31 32 bool spfa(int begin,int end){33     int u,v;34     queue
           
             q;35 for(int i=0;i<=end+2;i++){36 pre[i]=-1;37 vis[i]=0;38 dist[i]=inf;39 }40 vis[begin]=1;41 dist[begin]=0;42 q.push(begin);43 while(!q.empty()){44 u=q.front();45 q.pop();46 vis[u]=0;47 for(int i=head[u];i!=-1;i=edge[i].next){48 if(edge[i].c>0){49 v=edge[i].v;50 if(dist[v]>dist[u]+edge[i].cost){51 dist[v]=dist[u]+edge[i].cost;52 pre[v]=i;53 if(!vis[v]){54 vis[v]=true;55 q.push(v);56 }57 }58 }59 }60 }61 return dist[end]!=inf;62 }63 64 int MCMF(int begin,int end){65 int ans=0,flow;66 int flow_sum=0;67 while(spfa(begin,end)){68 flow=inf;69 for(int i=pre[end];i!=-1;i=pre[edge[i].u])70 if(edge[i].c