UVA 10779 Collectors Problem

題目簡述：
你和一群人都有一些貼紙，然後你想要越多不同種貼紙，所以你設法和這些人做交易
每次交易都是一張貼紙換一張貼紙，交易是成立的若且唯若且(1)你給他的貼紙是他沒有的(2)他給你的貼紙是多出來的

給定初始狀態，問最後最多可以有多少種貼紙？

總之就是設好幾個限制

(1) 固定人，對於每種貼紙都有上限為1的進入限制。
設好一些邊：
(2) 代表貼紙交換的邊
(3) 每種貼紙最多只會流出1張
(4) 每個人願意交出的貼紙是原本的少一個

若這樣設定，每一條流就會是一次貼紙的交換

testdata:

100
2 2
3 1 1 1
2 2 2

2 2
3 1 1 1
2 2 1

3 3
3 1 1 1
2 2 2
2 2 3

2 3
3 1 2 2
2 3 3




#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 100000
using namespace std;
typedef long long int int64;
int indc; int getind(){return indc++;} int getcnt(){return indc;}
struct edge{int a, b, c;}es[500000]; int ecnt;
vector<int> to[100000]; int nn;
void init(int n){
nn = n;
for(int lx = 0;lx < n;lx++)
to[lx].clear();
ecnt = 0;
return;
}
void addedge(int a, int b, int ab, int ba=0){
if((ab == 0) and (ba == 0)) return;
es[ecnt].a = a, es[ecnt].b = b, es[ecnt].c = ab; to[a].push_back(ecnt++);
es[ecnt].a = b, es[ecnt].b = a, es[ecnt].c = ba; to[b].push_back(ecnt++);
return;
}
int dis[100000];
int path[100000];
int post[100000];
int que[100000];
int bfs(int s, int t){
for(int lx = 0;lx < nn;lx++)
dis[lx] = -1, post[lx] = -1;
int qs = 0, qe = 1; que[0] = s, dis[s] = 0;
while(qs < qe){
int gg = que[qs++];
for(int lx = 0;lx < to[gg].size();lx++){
int lind = to[gg][lx];
if(es[lind].c <= 0) continue;
int pind = es[lind].b;
if(dis[pind] != -1) continue;
dis[pind] = dis[gg] + 1;
post[pind] = lind;
que[qe++] = pind;
}
}
if(dis[t] == -1) return 0;
int pgg = t;
int mm = 10000;
int pathcnt = 0;
while(pgg != s){
int lid = post[pgg];
mm = min(mm, es[lid].c);
path[pathcnt++] = lid;
pgg = es[lid].a;
}
for(int lx = 0;lx < pathcnt;lx++){
es[path[lx]].c -= mm;
es[path[lx]^1].c += mm;
}
return mm;
}
int EKarp(int s, int t){
int cc = 0;
for(;;){
int dc = bfs(s, t);
if(dc == 0) break;
cc += dc;
}
return cc;
}
void pes(){
for(int lx = 0;lx < ecnt;lx++)
if(es[lx].c)
printf("%d -> %d w = %d\n", es[lx].a, es[lx].b, es[lx].c);
return;
}
int main()
{
int T;scanf("%d", &T);
for(int lt = 0;lt < T;lt++){
int n, m;scanf("%d %d", &n, &m);
int own[40][100];

memset(own, 0, sizeof(own));
for(int lx = 0;lx < n;lx++){
int acnt = 0;scanf("%d", &acnt);
for(int la = 0;la < acnt;la++){
int inp;scanf("%d", &inp);
own[lx][inp-1]++;
}
}
int pstin[20][30], pstout[20][30], pvin[20][30], pvout[20][30];
int lim[100];
indc = 0;int st = getind(), ed = getind();
for(int lx = 0;lx < m;lx++){
lim[lx] = getind();
//printf("lim%d = %d\n", lx, lim[lx]);
}
for(int lx = 0;lx < n;lx++){
for(int lm = 0;lm < m;lm++){
pstin[lx][lm] = getind();
pstout[lx][lm] = getind();
pvin[lx][lm] = getind();
pvout[lx][lm] = getind();
// printf("%d->%d X %d->%d\n", pvin[lx][lm], pvout[lx][lm], pstin[lx][lm], pstout[lx][lm]);
}
//printf("--\n");
}
init(getcnt());
//printf("pcnt = %d\n", getcnt());
for(int lx = 0;lx < m;lx++){
addedge(st, pstout[0][lx], own[0][lx]);
addedge(lim[lx], ed, 1);
}
for(int lx = 1;lx < n;lx++){
for(int lm = 0;lm < m;lm++){
addedge(pvin[lx][lm], pvout[lx][lm], 1-(own[lx][lm]>0));
if(own[lx][lm] > 1)
addedge(pstin[lx][lm], pstout[lx][lm], own[lx][lm]-1);
}
for(int lm1 = 0;lm1 < m;lm1++)
for(int lm2 = 0;lm2 < m;lm2++)
if(lm1 != lm2)
addedge(pvout[lx][lm1], pstin[lx][lm2], 1);
for(int ly = 1;ly < n;ly++){
if(lx == ly) continue;
for(int lm = 0;lm < m;lm++){
addedge(pstout[lx][lm], pvin[ly][lm], 1);
addedge(pstout[lx][lm], lim[lm], 1);
}
}
}
for(int lx = 1;lx < n;lx++)
for(int lm = 0;lm < m;lm++)
addedge(pstout[0][lm], pvin[lx][lm], 1);
for(int lx = 0;lx < n;lx++)
for(int lm = 0;lm < m;lm++)
addedge(pstout[lx][lm], lim[lm], 1);
//pes();
int ans = EKarp(st, ed);
if(ans > m) printf("%d\n", 1/0);
printf("Case #%d: %d\n", lt+1, ans);
}
return 0;
}