电源

POJ 1087 A Plug for UNIX 最大流

2019-07-14 02:07发布

站内文章 / 电源技术
15292 0 1759
http://poj.org/problem?id=1087 题意：大概就是一个房间有很多类型的插座，有很多要插专门类型插座的电器，和一堆转换头，求最少的无法充电的电器数。 题解：网络流。 建图：假设出超级源点s（0）与超级汇点t（400）。 原点与电器相连，容量为1，汇点与电源相连，容量为1，类相同的电源与电器相连，容量为1，有转换头的电源相连，容量为inf。 样例如图：（灵魂画手） 一开始困扰我的是转换头的问题。把B电源转换成了C电源，我总想让C指向B，但实际上B转化成C电源，那么B电源就被用了，所以按照网络流的方向，应该是从B指向C。 另一个坑就是这题的点的编号不能连续编号，除非你把电源序号排在最后面，因为一开始的电源数不是最终的电源数，中间可能冒出来一个之前没有的X之类的。 代码： #include #include #include #include #include #include #define inf 0x3f3f3f #define maxN 500 #define maxM 800 using namespace std; class Graph { private: int s,t; int cnt; int Head[maxN]; int Next[maxM]; int V[maxM]; int W[maxM]; int Depth[maxN]; public: int n; void init(int nn,int ss,int tt)//初始化 { n=nn; s=ss; t=tt; cnt=-1; memset(Head,-1,sizeof(Head)); memset(Next,-1,sizeof(Next)); return; } void _Add(int u,int v,int w) { cnt++; Next[cnt]=Head[u]; V[cnt]=v; W[cnt]=w; Head[u]=cnt; } void Add_Edge(int u,int v,int w)//加边，同时加正向和反向的 { _Add(u,v,w); _Add(v,u,0); } int dfs(int u,int dist) { //cout<<"Dfs:"<0) { W[i]-=di; W[i^1]+=di; return di; } } } return 0; } int bfs() { //cout<<"Bfs.begin:"< Q; while (!Q.empty()) Q.pop(); memset(Depth,0,sizeof(Depth)); Depth[s]=1; Q.push(s); do { int u=Q.front(); //cout<0)&&(Depth[V[i]]==0)) { Depth[V[i]]=Depth[u]+1; Q.push(V[i]); } } } while (!Q.empty()); //cout<<"Bfs.end"<0) return 1; return 0; } int Dinic() { int Ans=0; while (bfs()) { while (int d=dfs(s,inf)) Ans+=d; } return Ans; } }; map mp; int tot; int getid(string s){ if(mp[s]==0)mp[s]=++tot; return mp[s]; } int main() { Graph G; int nn,i,m,f; string s1,s2; G.init(405,0,400); scanf("%d",&nn); for(i=1;i<=nn;i++){ cin>>s1; getid(s1); G.Add_Edge(getid(s1),400,1); } scanf("%d",&m); for(i=1;i<=m;i++){ cin>>s1>>s2; G.Add_Edge(i+100,getid(s2),1); G.Add_Edge(0,i+100,1); } scanf("%d",&f); for(i=1;i<=f;i++){ cin>>s1>>s2; G.Add_Edge(getid(s1),getid(s2),inf); } printf("%d ",m-G.Dinic()); return 0; }  

热门文章