ZOJ@2616題意：政府拍賣n個無線頻道，兩公司競爭，分別提出一些組合的競標(biāo)，每個標(biāo)單需要多個無線頻道，同一家公司提出標(biāo)單之間不沒有共同的頻道，兩個公司的標(biāo)單可能競爭同一個頻道。求政府最大收益？
解法：二分圖，兩邊分別兩公司的標(biāo)單，有競爭的標(biāo)單之間連邊，容量為無窮大。添加一個匯點，連第一家公司的標(biāo)單，容量為標(biāo)單價格；同理添加一個匯...。所求結(jié)果為所有標(biāo)單總價值-最大流。
// 2390064 2011-01-21 10:19:41 Accepted 2616 C++ 4790 4256 redsea
// Dinic最大流 O(V^2 * E)
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
#define N 6002
#define E N*33
#define typec int // type of cost
const typec inf = 30000000; // max of cost
struct edge {
int x, y, nxt; typec c;
}bf[E];
int ne, head[N], cur[N], ps[N], dep[N];
vector<int>v1[3001];
vector<int>v2[3001];
int value1[3001], value2[3001];
void addedge(int x, int y, typec c)
{
// add an arc(x -> y, c); vertex: 0 ~ n-1;
bf[ne].x = x; bf[ne].y = y; bf[ne].c = c;
bf[ne].nxt = head[x]; head[x] = ne++;
bf[ne].x = y; bf[ne].y = x; bf[ne].c = 0;
bf[ne].nxt = head[y]; head[y] = ne++;
}
typec flow(int n, int s, int t)
{
typec tr, res = 0;
int i, j, k, f, r, top;
while (1) {
memset(dep, -1, n * sizeof(int));
for (f = dep[ps[0] = s] = 0, r = 1; f != r; )
for (i = ps[f++], j = head[i]; j; j = bf[j].nxt)
{
if (bf[j].c && -1 == dep[k = bf[j].y]){
dep[k] = dep[i] + 1; ps[r++] = k;
if (k == t) { f = r; break; }
}
}
if (-1 == dep[t]) break;
memcpy(cur, head, n * sizeof(int));
for (i = s, top = 0; ; ) {
if (i == t) {
for (k = 0, tr = inf; k < top; ++k)
if (bf[ps[k]].c < tr)
tr = bf[ps[f = k]].c;
for (k = 0; k < top; ++k)
bf[ps[k]].c -= tr, bf[ps[k]^1].c += tr;
res += tr; i = bf[ps[top = f]].x;
}
for (j=cur[i]; cur[i]; j = cur[i] = bf[cur[i]].nxt)
if (bf[j].c && dep[i]+1 == dep[bf[j].y])break;
if (cur[i]) {
ps[top++] = cur[i];
i = bf[cur[i]].y;
}
else {
if (0 == top) break;
dep[i] = -1; i = bf[ps[--top]].x;
}
}
}
return res;
}
bool check(int x, int y)
{
int i = 0, j = 0;
while(i<v1[x].size()&&j<v2[y].size())
{
if(v1[x][i] < v2[y][j])
i++;
else if(v1[x][i] > v2[y][j])
j++;
else
return true;
}
return false;
}
int main()
{
int T, x, nbuf, n, m, value;
scanf("%d",&T);
char buf[1000];
char *p;
int tcase = 0;
while(T--)
{
scanf("%d",&n);
for(int i = 1; i <= n; i++){
v1[i].clear();
scanf("%d",&value1[i]);
scanf("%[^\n]",buf);
p = buf;
while(sscanf(p,"%*[^-0-9]%d%n",&value,&x)>0)
{
p += x;
v1[i].push_back(value);
}
sort(v1[i].begin(),v1[i].end());
}
scanf("%d",&m);
for(int i = 1; i <= m; i++){
v2[i].clear();
scanf("%d",&value2[i]);
scanf("%[^\n]",buf);
p = buf;
while(sscanf(p,"%*[^0-9]%d%n",&value,&x)>0)
{
p += x;
v2[i].push_back(value);
}
sort(v2[i].begin(),v2[i].end());
}
memset(head,0,sizeof(head));
ne = 2;
int total = 0;
for(int i = 1; i <= n; i++){
total += value1[i];
addedge(0, i, value1[i]);
}
for(int i = 1; i <= m; i++){
total += value2[i];
addedge(n+i,n+m+1,value2[i]);
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(check(i,j)){
addedge(i,j+n,inf);
}
}
}
printf("Case %d:\n%d\n",++tcase,total-flow(n+m+2,0,n+m+1));
if(T)
printf("\n");
}
return 0;
}