电源

poj 1087 最大流（让尽可能多的电器能够供电）

2019-07-14 03:30发布

站内文章 / 电源技术
12566 0 916
题意：有插座和电器两种物品。首先有n种插座，n种插座用字符串表示，这n种插座可以理解为是插在电源上的插座。然后有m个电器，现在电器要充电，电器用字符串表示，每个电器都有自己可以插（且只可以插）的插座(这个插座可以不是那n个插在电源上的插座，可以是其他的插座)。现在有k个信息，s1 s2代表s1插座可以插到s2插座上去，这里类似于将插头转换了一下，这些s1与s2也可以不是那n个插在电源上的插座。给出这些个信息问你在尽可能满足多得电器工作的情况下还有多少个电器没有插座可以用。 思路：最大流，这样建图：建一个源点，指向所有电器，容量为1；所有电器指向他们可以插的那个插头上，容量为1；如果一个插头可以插到另一个插头，那么将s1指向s2，容量为无限大（因为这种转换器有无限多个）；将所有插在电源上的插头指向汇点，容量为1。然后从源点到汇点求最大流即可。输出电器的数量-最大流。 题目中电器和插座都用字符串表示，所以使用stl的map比较方便。 #include #include #include #include #include #define INF 0x3ffffff #define N 805 using namespace std; int m,n,first[N],a[N],p[N],id[N],q[2000],top; char s[25],t[25]; mapmm; struct edge{ int y,f,next; }e[8000]; void add(int x,int y,int f){ e[top].y = y; e[top].f = f; e[top].next = first[x]; first[x] = top++; e[top].y = x; e[top].f = 0; e[top].next = first[y]; first[y] = top++; } int maxflow(int s,int t){ int i,now,rear,front,res=0; while(1){ front = rear = -1; memset(a,0, sizeof(a)); memset(p, 0, sizeof(p)); a[s] = INF; q[++rear] = s; while(front < rear){ now = q[++front]; for(i = first[now];i!=-1;i=e[i].next) if(!a[e[i].y] && e[i].f){ a[e[i].y] = min(a[now] , e[i].f); p[e[i].y] = now; id[e[i].y] = i; q[++rear] = e[i].y; } } if(!a[t]) break; res += a[t]; for(i = t;i!=s;i=p[i]){ e[id[i]].f -= a[t]; e[id[i]^1].f += a[t]; } } return res; } int main(){ int i,k,w; memset(first,-1,sizeof(first)); top = 0; scanf("%d",&n); for(i = 1;i<=n;i++){ scanf("%s",s); mm[s] = i; } k = n; scanf("%d",&m); for(i = 1;i<=m;i++){ scanf("%s %s",s,t); if(!mm.count(t))//新的插座，加入map mm[t] = ++k; add(i,m+mm[t],1);//电器和插座的容量为1 } scanf("%d",&w); for(i = 1;i<=w;i++){ scanf("%s %s",s,t); if(!mm.count(s))//新的插座加入map mm[s] = ++k; if(!mm.count(t)) mm[t] = ++k; add(m+mm[s] ,m+mm[t],INF);//插座转换器有无限多个，所以INF } for(i = 1;i<=m;i++) add(0,i,1);//源点到电器的边 for(i = m+1;i<=m+n;i++) add(i,m+k+1,1);//（有权利通电的）插座到汇点的边 printf("%d ",m-maxflow(0,m+k+1)); return 0; }