A Plug for UNIX POJ - 1087(模板题 没啥好说的。。就用了一个map)

题意:

几种插头,每一种都只有一个,但有无限个插头转换器,转换器(a,b) 意味着 可以把b转换为a,有几个设备,每个设备对应一种插头,求所不能匹配插头的设备数量

这个题可以用二分图做 , 我用的是最大流,最后用设备数 减去 最大匹配数即可

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#define mem(a, b) memset(a, b, sizeof(a))
using namespace std;
const int maxn = , INF = 0x7fffffff;
int head[maxn], d[maxn], cur[maxn];
int n, m, s, t, z;
int cnt;
map<string, int> mapp;
struct node{
int u, v, c, next;
}Node[maxn*]; void add_(int u, int v, int c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].c = c;
Node[cnt].next = head[u];
head[u] = cnt++;
} void add(int u, int v, int c)
{
add_(u, v, c);
add_(v, u, );
} bool bfs()
{
queue<int> Q;
mem(d, );
Q.push(s);
d[s] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i=head[u]; i!=-; i=Node[i].next)
{
node e = Node[i];
if(!d[e.v] && e.c > )
{
d[e.v] = d[e.u] + ;
Q.push(e.v);
// cout<< u << " " << e.v << " " << t <<endl;
if(e.v == t) break;
}
}
}
return d[t] != ;
} int dfs(int u, int cap)
{
// cout<< cap <<endl;
if(u == t || cap == )
return cap;
int ret = ;
for(int &i=cur[u]; i!=-; i=Node[i].next)
{
node e = Node[i];
if(d[e.v] == d[e.u] + && e.c > )
{
int V = dfs(e.v, min(cap, e.c));
Node[i].c -= V;
Node[i^].c += V;
cap -= V;
ret += V;
// cout<< V <<endl;
if(cap == ) break;
}
}
return ret;
} int dinic()
{
int ans = ;
while(bfs())
{
memcpy(cur, head, sizeof(head));
ans += dfs(s, INF);
// cout<< ans <<endl;
}
return ans;
}
int main()
{
cin>> n;
mem(head, -);
s = , t = n + *m + *z + ;
for(int i=; i<=n; i++)
{
string str;
cin>> str;
mapp[str] = i;
add(s, i, );
}
cin>> m;
for(int i=; i<=m; i++)
{
string str, sstr;
cin>> str >> sstr;
add(n+i, n+m+i, );
add(n+m+i, t, INF);
if(!mapp[sstr])
{
mapp[sstr] = n + m* + i;
}
add(mapp[sstr], n+i, INF);
}
cin>> z;
for(int i=; i<=z; i++)
{
string u, v;
cin>> u >> v;
if(!mapp[u])
mapp[u] = n+*m+i;
if(!mapp[v])
mapp[v] = n+*m+z+i;
// add(s, mapp[v], INF);
add(mapp[v], mapp[u], INF);
}
// cout<< m << " " <<dinic() <<endl;
cout<< m - dinic() <<endl; return ;
}
上一篇:UVA 1663 Purifying Machine (二分图匹配,最大流)


下一篇:jQuery Mobile 1.1八大新特性介绍