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