中文题意不描述。
链接：http://wikioi.com/problem/1028/
这题一开始很裸的最大权二分匹配。但是原来没有接触过，KM的这个最大权不大会。然后一开始以为用最大费用最大流直接就能搞，后来知道单纯的费用流解决的是二分最佳匹配，而不是最大权，QCMM然后看了一下这个http://hi.baidu.com/lerroy312/item/42e718ba58a1f8df85dd795f
结果改了之后不对，不知道为什么最后用的最小费用，对边的权值取负值，结果取负值才过。。。不解。。。
1 #include <iostream> 2 #include <queue> 3 #include <iostream> 4 #include <cstdio> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 const int maxn = 350; 9 const int inf = 10000000; 10 struct node 11 { 12 int u,v,cap,flow,cost,next; 13 }edges[100050]; 14 int head[maxn],cnt; 15 void init(int n) 16 { 17 int i; 18 for(i = 0;i <= n;i++) 19 head[i] = -1; 20 cnt = 0; 21 22 return ; 23 } 24 void addedge(int u,int v,int cap,int cost) 25 { 26 edges[cnt].u = u; 27 edges[cnt].v = v; 28 edges[cnt].cap = cap; 29 edges[cnt].flow = 0; 30 edges[cnt].cost = cost; 31 edges[cnt].next = head[u]; 32 head[u] = cnt; 33 cnt++; 34 edges[cnt].u = v; 35 edges[cnt].v = u; 36 edges[cnt].cap = 0; 37 edges[cnt].flow = 0; 38 edges[cnt].cost = -cost; 39 edges[cnt].next = head[v]; 40 head[v] = cnt; 41 cnt++; 42 } 43 int vis[maxn],a[maxn],pre[maxn],dis[maxn]; 44 int spfa(int s,int t,int n,int &flow,int &cost) 45 { 46 int i; 47 queue<int> q; 48 for(i = 0;i <= n ;i++) 49 dis[i] = inf,vis[i] = 0; 50 51 dis[s] = 0; 52 pre[s] = 0; 53 vis[s] = 1; 54 a[s] = inf; 55 56 int u,v; 57 q.push(s); 58 59 while(!q.empty()) 60 { 61 u = q.front(); 62 q.pop(); 63 vis[u] = 0; 64 65 for(i = head[u];i != -1;i = edges[i].next) 66 { 67 struct node & e = edges[i]; 68 69 v = e.v; 70 if(e.cap > e.flow &&dis[v] > dis[u]+e.cost) 71 { 72 dis[v] = dis[u]+e.cost; 73 a[v] = min(a[u],e.cap-e.flow); 74 pre[v] = i; 75 if(!vis[v]) 76 { 77 vis[v] = 1; 78 q.push(v); 79 } 80 } 81 } 82 } 83 84 if(dis[t] >= inf) 85 return 0; 86 flow+= a[t]; 87 cost += dis[t]*a[t]; 88 u = t; 89 while(u != s) 90 { 91 edges[pre[u]].flow += a[t]; 92 edges[pre[u]^1].flow -= a[t]; 93 u = edges[pre[u]].u; 94 } 95 return 1; 96 } 97 int mcmf(int s,int t, int n) 98 { 99 int cost = 0,flow = 0; 100 while(spfa(s,t,n,flow,cost)); 101 102 return cost; 103 } 104 int main() 105 { 106 int n,m; 107 scanf("%d %d",&n,&m); 108 109 int i,j; 110 init(n+m+4); 111 for(i =1;i <= n;i++) 112 { 113 addedge(0,i,1,0); 114 for(j = 1;j <= m;j++) 115 { 116 int w; 117 scanf("%d",&w); 118 addedge(i,j+n,1,-w); 119 } 120 addedge(i,m+n+1,1,0); 121 } 122 addedge(n+m+1,m+n+2,n,0); 123 for(j = 1;j <= m;j++) 124 addedge(j+n,m+n+2,1,0); 125 cout<<-mcmf(0,m+n+2,m+n+3)<<endl; 126 return 0; 127 }
额，最近跟scu-frog神请教了下这个问题，scu-frog神看了下代码，说你的最长路的初始化有问题，有负权边为什么赋值-1.
然后默默对自己说了一句sb。。。默默改了交了一下，ac= =。
1 #include <iostream> 2 #include <queue> 3 #include <iostream> 4 #include <cstdio> 5 #include <cstring> 6 #include <vector> 7 using namespace std; 8 const int maxn = 350; 9 const int inf = 10000000; 10 struct node 11 { 12 int u,v,cap,flow,cost,next; 13 }edges[100050]; 14 int head[maxn],cnt; 15 void init(int n) 16 { 17 int i; 18 for(i = 0;i <= n;i++) 19 head[i] = -1; 20 cnt = 0; 21 22 return ; 23 } 24 void addedge(int u,int v,int cap,int cost) 25 { 26 edges[cnt].u = u; 27 edges[cnt].v = v; 28 edges[cnt].cap = cap; 29 edges[cnt].flow = 0; 30 edges[cnt].cost = cost; 31 edges[cnt].next = head[u]; 32 head[u] = cnt; 33 cnt++; 34 edges[cnt].u = v; 35 edges[cnt].v = u; 36 edges[cnt].cap = 0; 37 edges[cnt].flow = 0; 38 edges[cnt].cost = -cost; 39 edges[cnt].next = head[v]; 40 head[v] = cnt; 41 cnt++; 42 } 43 int vis[maxn],a[maxn],pre[maxn],dis[maxn]; 44 int spfa(int s,int t,int n,int &flow,int &cost) 45 { 46 int i; 47 queue<int> q; 48 for(i = 0;i <= n ;i++) 49 dis[i] = -inf,vis[i] = 0; 50 51 dis[s] = 0; 52 pre[s] = 0; 53 vis[s] = 1; 54 a[s] = inf; 55 56 int u,v; 57 q.push(s); 58 59 while(!q.empty()) 60 { 61 u = q.front(); 62 q.pop(); 63 vis[u] = 0; 64 65 for(i = head[u];i != -1;i = edges[i].next) 66 { 67 struct node & e = edges[i]; 68 69 v = e.v; 70 if(e.cap > e.flow &&dis[v] < dis[u]+e.cost) 71 { 72 dis[v] = dis[u]+e.cost; 73 a[v] = min(a[u],e.cap-e.flow); 74 pre[v] = i; 75 if(!vis[v]) 76 { 77 vis[v] = 1; 78 q.push(v); 79 } 80 } 81 } 82 } 83 84 if(dis[t] <= -inf) 85 return 0; 86 flow+= a[t]; 87 cost += dis[t]*a[t]; 88 u = t; 89 while(u != s) 90 { 91 edges[pre[u]].flow += a[t]; 92 edges[pre[u]^1].flow -= a[t]; 93 u = edges[pre[u]].u; 94 } 95 return 1; 96 } 97 int mcmf(int s,int t, int n) 98 { 99 int cost = 0,flow = 0; 100 while(spfa(s,t,n,flow,cost)); 101 102 return cost; 103 } 104 int main() 105 { 106 int n,m; 107 scanf("%d %d",&n,&m); 108 109 int i,j; 110 init(n+m+4); 111 for(i =1;i <= n;i++) 112 { 113 addedge(0,i,1,0); 114 for(j = 1;j <= m;j++) 115 { 116 int w; 117 scanf("%d",&w); 118 addedge(i,j+n,1,w); 119 } 120 addedge(i,m+n+1,1,0); 121 } 122 addedge(n+m+1,m+n+2,n,0); 123 for(j = 1;j <= m;j++) 124 addedge(j+n,m+n+2,1,0); 125 cout<<mcmf(0,m+n+2,m+n+3)<<endl; 126 return 0; 127 }