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 |
Re:痛苦ing,交了n次 floyd+2分图 哪里有问题呢 RE疯啦In Reply To:Re:痛苦ing,交了n次 floyd+2分图 哪里有问题呢 RE疯啦 Posted by:newton88518 at 2006-04-07 15:30:12 #include<iostream> #include<map> #include<string> using namespace std; #define M 500 bool v[M][M]; void floyd(bool x[][M],int lg) { int i,j,k; for(k=0;k<lg;k++) for(i=0;i<lg;i++) { if(!x[i][k]) continue; for(j=0;j<lg;j++) { if(!x[k][j]) continue; x[i][j]=1; } } } int match(bool u[][M],int vm1,int vm2) { int* v1=new int [vm1]; int* v2=new int [vm2]; int* pre=new int [vm2]; int* q=new int [vm2]; memset(v1,-1,vm1*sizeof(int)); memset(v2,-1,vm2*sizeof(int)); int i,j,s,e,x,sum=0; for(i=0;i<vm1;i++) { s=e=0; for(j=0;j<vm2;j++) pre[j]=-2; for(j=0;j<vm2;j++) if(v[i+vm2+1][j+1]) { pre[j]=-1; if(v2[j]==-1) { x=j; goto KML; } q[e++]=j; } while(s<e) { x=q[s]; if(v2[x]==-1) break; s++; for(j=0;j<vm2;j++) { if(pre[j]==-2 && v[v2[x]+vm2+1][j+1]) { pre[j]=x; q[e++]=j; } } } if(s==e) continue; while(pre[x]>-1) { v1[v2[pre[x]]]=x; v2[x]=v2[pre[x]]; x=pre[x]; } KML: v1[i]=x; v2[x]=i; sum++; } delete [] v1; delete [] v2; delete [] q; delete [] pre; return sum; } void solve() { int n; cin>>n; int i; string s; map<string,int> plug; map<string,int>::const_iterator p; for(i=1;i<=n;i++) { cin>>s; plug[s]=i; } int m,top; cin>>m; top=m+n; string sde,spg; int ns,np; pair<string,int> temp; for(i=n+1;i<=m+n;i++) { cin>>sde>>spg; if( (p=plug.find(spg))==plug.end() ) { ++top; plug[spg]=top; v[i][top]=1; } else { temp=(*p); v[i][temp.second]=1; } } int k,de,pg; cin>>k; for(i=0;i<k;i++) { cin>>sde>>spg; p=plug.find(sde); de=(*p).second; p=plug.find(spg); pg=(*p).second; v[de][pg]=1; } int start=top+1,end=0; for(i=n+1;i<=m+n;i++) v[start][i]=1; for(i=1;i<=n;i++) v[i][end]=1; floyd(v,start); int sum; sum=match(v,m,n); cout<<(m-sum)<<endl; } int main() { // freopen("a.in","r",stdin); solve(); return 0; } 好心人帮看看吧 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator