最小费用最大流 求的时候把边加为负的 输出的时候再负回来 就变成求的最大费用了

拆点 一个点拆为 i i' i->i'连两条边 一条cap为0 cost为给出的值 另一条cap为INF cost为0 ，i'到右和下分别设置一条边cap为INF cost为0 设置超级源点到1节点 cap为K cost为0

1 #include 
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define INF 0xfffffff 8 #define MN 50500 9 #define MM 100100 10 using namespace std; 11 struct node 12 { 13 int u,v,cost,cap,next; 14 }edge[MM]; 15 int head[MN],t,vis[MN],dist[MN],pp[MN]; 16 void init() 17 { 18 t =0; 19 memset(head,-1,sizeof(head)); 20 } 21 void add(int u,int v,int c,int p) 22 { 23 edge[t].u = u; 24 edge[t].v = v; 25 edge[t].cap = c; 26 edge[t].cost = p; 27 edge[t].next = head[u]; 28 head[u] = t++; 29 edge[t].u = v; 30 edge[t].v = u; 31 edge[t].cap = 0; 32 edge[t].cost = -p; 33 edge[t].next = head[v]; 34 head[v] = t++; 35 } 36 int spfa(int s,int en,int n) 37 { 38 int u,v,i; 39 memset(vis,0,sizeof(vis)); 40 memset(pp,-1,sizeof(pp)); 41 for(i = 0 ; i <= n ; i++) 42 dist[i] =INF; 43 queue
            
             q; 44 dist[s] = 0; 45 vis[s] = 1; 46 q.push(s); 47 while(!q.empty()) 48 { 49 u = q.front(); 50 q.pop(); 51 vis[u] = 0; 52 //cout<
             <
              
               dist[u]+edge[i].cost) 57 { 58 dist[v] = dist[u]+edge[i].cost; 59 pp[v] = i; 60 if(!vis[v]) 61 { 62 vis[v] = 1; 63 q.push(v); 64 } 65 } 66 } 67 } 68 //cout<
               
                <
                
                 edge[i].cap) 82 minf = edge[i].cap; 83 } 84 for(i = pp[en] ; i != -1; i = pp[edge[i].u]) 85 { 86 edge[i].cap -= minf; 87 edge[i^1].cap+=minf; 88 } 89 //cout<
                 
                  <<" "<
                  
                   <
                   
                    >n>>k) 98 { 99 init();100 int s = 0,en = 2*n*n+1;101 add(s,1,k,0);102 add(2*n*n,en,k,0);103 for(i = 1; i <= n ; i++)104 for(j = 1; j <= n ; j++)105 {106 cin>>a;107 add((i-1)*n+j,(i-1)*n+j+n*n,1,-a);108 add((i-1)*n+j,(i-1)*n+j+n*n,INF,0);109 if(i