这道题就是  的加强版

如果一开始把全部边连上会T

优化的方法是只连用到过和下一次增广可能用到的边。

1 #include
     
       2 using namespace std; 3 const int N=50,M=110,NN=100010,oo=1e9; 4 int n,m,cost[N][M],tot,s,t,p[N],rank[NN],c[NN]; 5 bool isend[NN]; 6 struct Edge{ 7     int from,to,flow,cap,w; 8 }; 9 int edge_tot;10 vector
      
       edge;11 vector
       
        point[NN];12 void add_edge(int f,int t,int cc,int ww){13     edge.push_back((Edge){f,t,0,cc,ww});14     point[f].push_back(edge_tot++);15     edge.push_back((Edge){t,f,0,0,-ww});16     point[t].push_back(edge_tot++);17     return;18 }19 int dis[NN],pre[NN];20 bool inq[NN];21 bool spfa(){22     queue
        
         q;23     int x;24     for(int i=1;i<=tot;i++) dis[i]=oo;25     q.push(s);26     dis[s]=0,inq[s]=1;27     while(!q.empty()){28         x=q.front();q.pop();29         inq[x]=0;30         for(int i=0;i