| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
数据开大点!!!map+网络流,附上代码。。#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
using namespace std;
int father[1020];
int c[1010][1010];
int f[1010][1010];
int l[1010][1010];
int m,n;
bool already[1010];
int times[1010];
int q[1010];
int total;
map<string,int> mymap;
map<string,int>::iterator it;
bool in_flow()
{
int start=0,end=0;
int temp;
memset(already,true,sizeof(already));
q[0]=0;
bool e;
already[0]=false;
while (start<=end)
{
e=false;
temp=q[start];
for (int i=1;i<=total+1;i++)
{
if (already[i] && l[temp][i]>0)
{
end++;
q[end]=i;
already[i]=false;
father[i]=temp;
if (i==total+1)
{
e=true;
break;
}
}
}
if (e)
break;
start++;
}
if (!e)
return false;
int k=total+1;
int minn=99999999;
while (k!=0)
{
if (minn>l[father[k]][k])
minn=l[father[k]][k];
k=father[k];
}
k=total+1;
while (k!=0)
{
f[father[k]][k]+=minn;
f[k][father[k]]=-f[father[k]][k];
l[k][father[k]]=c[k][father[k]]-f[k][father[k]];
l[father[k]][k]=c[father[k]][k]-f[father[k]][k];
k=father[k];
}
return true;
}
int main()
{
cin >> m;
memset(c,0,sizeof(c));
memset(l,0,sizeof(l));
memset(f,0,sizeof(f));
string s;
total=0;
int a,b;
int total1,total2;
while (m--)
{
cin >> s;
if (mymap.count(s)==0)
{
total++;
mymap.insert(make_pair(s,total));
times[total]=1;
}
else
{
it=mymap.find(s);
times[it->second]++;
}
}
total1=total;
cin >> m;
n=m;
string s1,s2;
while (m--)
{
cin >> s1 >> s2;
total++;
mymap.insert(make_pair(s1,total));
a=total;
l[0][total]=c[0][total]=1;
if (mymap.count(s2)==0)
{
total++;
mymap.insert(make_pair(s2,total));
}
it=mymap.find(s2);
b=it->second;
l[a][b]=c[a][b]=1;
}
cin >> m;
while (m--)
{
cin >> s1 >> s2;
if (mymap.count(s1)==0)
{
total++;
mymap.insert(make_pair(s1,total));
}
if (mymap.count(s2)==0)
{
total++;
mymap.insert(make_pair(s2,total));
}
it=mymap.find(s1);
a=it->second;
it=mymap.find(s2);
b=it->second;
l[a][b]=c[a][b]=99999999;
}
for (int i=1;i<=total1;i++)
l[i][total+1]=c[i][total+1]=times[i];
while (in_flow());
int sum=0;
for (int i=1;i<=total;i++)
if (f[0][i]>0)
sum+=f[0][i];
cout << n-sum << endl;
//system("pause");
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator