题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33631
题目大意：Bob有一些贴纸，他可以和别人交换，他可以把自己独有的贴纸拿出去，也可以把重复的贴纸拿出去（有时候把独有的贴纸而不是重复的贴纸拿出去能换到更多贴纸）。
Bob的朋友也有一些贴纸，但是他们只会拿自己重复的贴纸和Bob换，而且换的是自己没有的贴纸。
求Bob最后最多能有多少种贴纸。
解题思路：
题目意思很明确了。就算把重复的贴纸拿出去也不一定最优，贪心就不用尝试了。
全局资源调配得使用网络流模型。
建图方式：
①S点(看作是Bob)->所有物品：连一条边，cap是Bob持有贴纸数量。
②：所有朋友->所有物品：如果这个人持有的该贴纸数量>=2,连一条边,cap是贴纸数量-1。（原因是这些人只会把重复的贴纸拿出去）。
③：所有物品->所有朋友：如果这个人没有改物品，连一条边，cap=1,。(原因是这些人会接受自己没有的贴纸）
④：所有物品->T点：连一条边，cap=1，统计物品的种类。
这样建图之后，所有物品可以看作Bob的总资产，这个总资产可以流进，也可以流出，在这基础上做一次最大流，就是结果了。
代码使用比较坑爹的边表，虽然速度不如链式前向星，但是ISAP+gap优化+当前弧优化已经足够快了。
#include "cstdio"
#include "vector"
#include "cstring"
#include "queue"
using namespace std;
#define maxn 405
#define inf 100000000
struct Edge
{
int from,to,cap,flow;
Edge(int FROM,int TO,int CAP,int FLOW):from(FROM),to(TO),cap(CAP),flow(FLOW) {}
};
int d[maxn],p[maxn],gap[maxn],cur[maxn],paste[][];
bool vis[maxn];
vector<int> G[maxn];
vector<Edge> edges;
void addedge(int from,int to,int cap)
{
edges.push_back(Edge(from,to,cap,));
edges.push_back(Edge(to,from,,));
int m=edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
void bfs(int s,int t)
{
memset(vis,false,sizeof(vis));
memset(d,,sizeof(d));
memset(p,,sizeof(p));
d[t]=;vis[t]=true;
queue<int> Q;Q.push(t);
while(!Q.empty())
{
int u=Q.front();Q.pop();
for(int v=;v<G[u].size();v++)
{
Edge e=edges[G[u][v]^];
if(!vis[e.from]&&e.cap>e.flow)
{
vis[e.from]=true;
d[e.from]=d[u]+;
Q.push(e.from);
}
}
}
}
int augment(int s,int t)
{
int x=t,a=inf;
while(x!=s)
{
Edge e=edges[p[x]];
a=min(a,e.cap-e.flow);
x=e.from;
}
x=t;
while(x!=s)
{
edges[p[x]].flow+=a;
edges[p[x]^].flow-=a;
x=edges[p[x]].from;
}
return a;
}
int maxflow(int s,int t)
{
int flow=,u=s;
bfs(s,t);
memset(gap,,sizeof(gap));
memset(cur,,sizeof(cur));
for(int i=;i<=t;i++) gap[d[i]]++;
while(d[s]<t+)
{
if(u==t)
{
flow+=augment(s,t);
u=s;
}
bool flag=false;
for(int v=cur[u];v<G[u].size();v++) //Advance
{
Edge e=edges[G[u][v]];
if(e.cap>e.flow&&d[u]==d[e.to]+)
{
flag=true;
p[e.to]=G[u][v];
cur[u]=v;
u=e.to;
break;
}
}
if(!flag) //Retreat
{
int m=t+;
for(int v=;v<G[u].size();v++)
{
Edge e=edges[G[u][v]];
if(e.cap>e.flow) m=min(m,d[e.to]);
}
if(--gap[d[u]]==) break;
gap[d[u]=m+]++;
cur[u]=;
if(u!=s) u=edges[p[u]].from;
}
}
return flow;
}
int main()
{
int T,n,k,id,num,no=;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
scanf("%d",&num);
for(int j=;j<=num;j++)
{
scanf("%d",&id);
paste[i][id]++;
}
}
for(int i=;i<=k;i++) //S->Bob
if(paste[][i]) {addedge(,i,paste[][i]);}
for(int i=;i<=n;i++) //Bob->friends
for(int j=;j<=k;j++)
{
if(paste[i][j]>=) addedge(k+i,j,paste[i][j]-);
if(!paste[i][j]) addedge(j,k+i,);
}
for(int i=;i<=k;i++) addedge(i,k+n+,);//Bob->T
printf("Case #%d: %d\n",++no,maxflow(,k+n+));
for(int i=;i<maxn;i++) G[i].clear();
edges.clear();
memset(paste,,sizeof(paste));
}
}
| 2817630 | neopenx | UVA 10779 | Accepted | 0 KB | 16 ms | C++ 4.8.2 | 3270 B | 2014-10-05 13:48:15 |