网络流
2009-09-13 10:19:02| 分类:
资料
| 标签:
|举报
|字号大中小 订阅
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
#define inf 1000000000
#define MAXN 105
int mat[MAXN][MAXN],flow[MAXN][MAXN];
int pig[1003][MAXN];
int N,M;
int solve()
{
int pre[MAXN],que[MAXN],d[MAXN];
int i,j,t=N+2,s=1;
for(i=0;i<=N+2;i++)
for(j=0;j<=N+2;j++)
flow[i][j]=0;
while(1)
{
memset(pre,0,sizeof(pre));
int head=0,tail=1;
pre[s]=s;
d[s]=inf;
que[0]=s;
while(head<tail && pre[t]==0)
{
i=que[head];
for(j=1;j<=N+2;j++)
{
if(pre[j]==0)
{
if(mat[i][j]>flow[i][j])
{
pre[j]=i;
que[tail]=j;
d[j]=d[i]<mat[i][j]-flow[i][j]?d[i]:mat[i][j]-flow[i][j];
tail++;
}
else if(flow[j][i]>0)
{
pre[j]=-i;
que[tail]=j;
d[j]=d[i]<flow[j][i]?d[i]:flow[j][i];
tail++;
}
}
}
head++;
}
if(pre[t]==0){break;}
i=t;
while(i!=s)
{
j=abs(pre[i]);
if(pre[i]>0){flow[j][i]+=d[t];}
else{flow[i][j]-=d[t];}
i=j;
}
}
int ans=0;
for(i=1;i<=N+2;i++)
{
ans+=flow[s][i];
}
printf("%d\n",ans);
return 0;
}
int main()
{
int i,j;
while(scanf("%d%d",&M,&N)!=EOF)
{
for(i=1;i<=M;i++)
{
scanf("%d",&pig[i][1]);
pig[i][103]=1;
}
for(i=2;i<=N+1;i++)
{
int A;
scanf("%d",&A);
for(j=1;j<=A;j++)
{
int key;
scanf("%d",&key);
if(pig[key][103]==1){mat[1][i]+=pig[key][1];}
int k;
for(k=pig[key][103];k>=2;k--){
mat[pig[key][k]][i]=inf;
}
pig[key][++pig[key][103]]=i;
}
int B;
scanf("%d",&B);
mat[i][N+2]=B;
}
solve();
}
}
评论这张
转发至微博
转发至微博
评论