POJ 1087 A Plug for UNIX(最大流)
http://poj.org/problem?id=1087
题意:
有m个设备需要插座(给出了每个设备需要的插座型号),但是现在只有n个插座(任意两个插座类型不相同,因为题目说每种类型插座就一个),且给你k个转换器(转换器(u,v)可以使得插座v变成插座u),问你最多有几个设备没有插座可用?
分析:
建图:
源点s(编号0)到每个设备i有边 (s,i,1).
每个插座到j到汇点t(编号n+m+1)有边 (j,t,1)
如果设备i对应的插座是j,那么有边(i,j,1)
如果转换器对应(u,v),那么有边(u,v,INF) (因为转换器无限个,且它可以把原本需要u插座的电器连到v插座上)
最终用m-最大流 就是没插座可用的电器数.
题目有个陷阱:初始给你n个不同的插座,但是后续可能给出像样例中的x类型的插座(x并未在初始的n个插座中出现过),基于n<=100,m<=100,且k<=100
所以我们推断不同的插座数目最多300(其实应该推断400,但是测试发现数据最多300插座),所以插座编号直接从1到300预留位置,而电器编号直接从300-400预留位置,汇点t直接用401表示.
AC代码:
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#include<iostream>
#define INF 1e9
using namespace std;
const int maxn=405;
struct Edge
{
int from,to,cap,flow;
Edge(){}
Edge(int f,int t,int c,int fl):from(f),to(t),cap(c),flow(fl){}
};
struct Dinic
{
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int cur[maxn];
int d[maxn];
bool vis[maxn];
void init(int n,int s,int t)
{
this->n=n, this->s=s, this->t=t;
edges.clear();
for(int i=0;i<n;i++) G[i].clear();
}
void AddEdge(int from,int to,int cap)
{
edges.push_back( Edge(from,to,cap,0) );
edges.push_back( Edge(to,from,0,0) );
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BFS()
{
queue<int> Q;
memset(vis,0,sizeof(vis));
d[s]=0;
vis[s]=true;
Q.push(s);
while(!Q.empty())
{
int x=Q.front(); Q.pop();
for(int i=0;i<G[x].size();i++)
{
Edge& e=edges[G[x][i]];
if(!vis[e.to] && e.cap>e.flow)
{
vis[e.to]=true;
d[e.to]=d[x]+1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x,int a)
{
if(x==t ||a==0) return a;
int flow=0,f;
for(int& i=cur[x];i<G[x].size();++i)
{
Edge& e=edges[G[x][i]];
if(d[e.to]==d[x]+1 && (f=DFS(e.to,min(a,e.cap-e.flow) ) )>0)
{
e.flow +=f;
edges[G[x][i]^1].flow -=f;
flow +=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
int max_flow()
{
int ans=0;
while(BFS())
{
memset(cur,0,sizeof(cur));
ans += DFS(s,INF);
}
return ans;
}
}DC;
map<string,int> mp;//插座与编号的映射
int num;//当前不同的插座数
int ID(string& s)
{
if(mp.find(s)==mp.end())
mp[s]=++num;
return mp[s];
}
int main()
{
int n,m,k;
while(scanf("%d",&n)==1)
{
num=0;
mp.clear();
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
ID(s);
}
scanf("%d",&m);
int src=0, dst=400+1;
DC.init(402,src,dst);
for(int i=1;i<=n;i++) DC.AddEdge(i,dst,1);//插座的编号是从1开始的
for(int i=1;i<=m;i++)//电器的编号是从301开始的
{
string s1,s2;
cin>>s1>>s2;
DC.AddEdge(i+300,ID(s2),1);
DC.AddEdge(src,i+300,1);
}
int k;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
string s1,s2;
cin>>s1>>s2;
DC.AddEdge(ID(s1),ID(s2),INF);
}
printf("%d\n",m-DC.max_flow());
}
return 0;
}
分享到:
相关推荐
POJ1087的解题报告,内附详细源码和解题报告说明,有价值
poj1087贪心算法实验报告 poj1087贪心算法实验报告
poj2516代码最小费用最大流
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1584-A Round Peg in a Ground Hole 解题报告+AC代码
【二分图顶点覆盖->最小割->最大流->Dinic算法求解】 解题报告+AC代码 http://hi.csdn.net/!s/WKVPR0 ----> 我的所有POJ解题报告 http://blog.csdn.net/lyy289065406/article/details/6642573
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1942-Paths on a Grid 解题报告+AC代码
北大POJ2488-A Knight's Journey 解题报告+AC代码
poj分类poj分类poj分类poj分类
北大POJ2031-Building a Space Station【Prim+计算几何】 POJ2031-Building a Space Station【Prim+计算几何】
北大POJ1005-I Think I Need a Houseboat 解题报告+AC代码
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
北大POJ1159-Palindrome 解题报告+AC代码
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告