Posted on 2010-08-18 20:07
acronix 阅读(396)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：n个接口不同的插板，m个有用电器有各自的接口，k种可进行接口转换的适配器（数量不限），问最少多少个用电器不能用电（同时）。
分析：直接转换为典型的最大流问题，源点汇点自定，不同类型接口的插板与汇点相连权值为1；用电器与源点相连，权值为一；适配器的接口之间相连，权值为无穷大。建完图后，dinic模板一贴，完美解决。
注意：接口类型为字符串，用map映射转换。
cpp代码：
#include<iostream>
#include <cstdio>
#include <map>
#include <string>
#include <memory.h>
using namespace std;
map <string,int> mp;
const int inf = 0x7ffffff;
#define Max 605
int flow[Max][Max],d[Max],cnt; //flow is the network
int sta,end,N; //sta is the sourse ,end is the end,N is the number of vector
bool bfs(int s)
{
int front=0,rear=0;
int q[Max];
memset(d,-1,sizeof(d)); //d[] is the deep
q[rear++]=s; d[s]=0;
while(front<rear)
{
int k=q[front++];
for(int i=0;i<=N;i++)
if(flow[k][i]>0&&d[i]==-1){
d[i]=d[k]+1;
q[rear++]=i;
}
}
if(d[end]>=0) return true;
return false;
}
int dinic(int k,int sum) //k is the sourse
{
if (k==end)
return sum;
int os = sum;
for(int i=0;i<=N&∑i++)
if(d[i]==d[k]+1&&flow[k][i]>0)
{
int a=dinic(i,min(sum,flow[k][i])); //Deep to the end.
flow[k][i] -= a;
flow[i][k] += a;
sum -= a;
}
return os-sum;
}
int main()
{
int i,j,n,m,k;
char s[30],se[30];
sta = 0; end = N = Max - 1;
while (scanf("%d",&n) != EOF)
{
memset(flow,0,sizeof(flow));
mp.clear();
cnt = 0;
//读入插座类型
for (i = 1; i <= n; i++)
{
scanf("%s",s);
if (mp.count(s) == 0)
mp[s] = ++cnt;
flow[mp[s]][end] ++;
}
//读入用电器类型
scanf("%d",&m);
for (i = 1; i <= m; i++)
{
scanf("%s",s);
scanf("%s",s);
if (mp.count(s) == 0)
mp[s] = ++cnt;
flow[sta][mp[s]] ++;
}
//读入适配器类型
scanf("%d",&k);
for (i = 1; i <= k; i++)
{
scanf("%s %s",s,se);
if (mp.count(s) == 0)
mp[s] = ++cnt;
if (mp.count(se) == 0)
mp[se] = ++cnt;
flow[mp[s]][mp[se]] = inf;
}
int ret = 0;
while(bfs(sta))
ret += dinic(sta,inf);
printf("%d\n",m - ret);
}
return 0;
}