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 |
wa死了,高手帮忙给看一下:#include <iostream> #include <fstream> using namespace std; const int MAX=10100; struct kind{ int food,drink; } cok[MAX]; int kn; //kind number int ftype,dtype,n; int cfood[110][MAX]; //一只牛对应最多MAX种food int matfd[110],matdk[110]; int matx[110]; int tmfood[110],tmdrink[110]; int path(int u){ if(u<=0)return 0; int v; for(v=0;v<kn;v++){ int tpfood=cok[v].food; int tpdrink=cok[v].drink; if(cfood[u][v]==1&&tmfood[tpfood]<0&&tmdrink[tpdrink]<0){ tmfood[tpfood]=1; tmdrink[tpdrink]=1; // cout<<"TRY:"<<u<<" "<<tpfood<<" "<<tpdrink<<endl; if((matfd[tpfood]<0||matfd[tpfood]==u) //当前节点没有被占用或者被自己占用 &&(matdk[tpdrink]<0||matdk[tpdrink]==u) ||path(matfd[tpfood]) //存在一条新的从当前的父节点引出的路径 ||path(matdk[tpdrink]) ){ matx[u]=cok[v].food*(dtype+1)+cok[v].drink; matfd[tpfood]=u; matdk[tpdrink]=u; // cout<<"Success :"<<u<<" "<<tpfood<<" "<<tpdrink<<endl; return 1; } } } return 0; } int maxmatch(){ memset(matx,-1,sizeof(matx)); memset(matfd,-1,sizeof(matfd)); memset(matdk,-1,sizeof(matdk)); int i,j,ans=0; for(i=1;i<=n;i++){ if(matx[i]<0){ memset(tmfood,-1,sizeof(tmfood)); memset(tmdrink,-1,sizeof(tmdrink)); ans+=path(i); } } return ans; } int srch(kind tmp){ int i; for(i=0;i<kn;i++){ if(cok[i].drink==tmp.drink&&cok[i].food==tmp.food)return i; } return -1; } int main(){ // ifstream cin("data.txt"); cin>>n>>ftype>>dtype; int i,j,k; kn=0; memset(cfood,0,sizeof(cfood)); for(i=1;i<=n;i++){ int fd,dk; int d[110],f[110]; cin>>fd>>dk; for(j=0;j<fd;j++){ cin>>f[j]; } for(j=0;j<dk;j++){ cin>>d[j]; } for(j=0;j<fd;j++){ for(k=0;k<dk;k++){ kind tk; tk.food=f[j];tk.drink=d[k]; int res=srch(tk); if(res==-1){ cok[kn++]=tk; cfood[i][kn-1]=1; }else{ cfood[i][res]=1; } // cout<<i<<" "<<tmp<<endl; } } } /* for(i=0;i<kn;i++){ cout<<cok[i].food<<" "<<cok[i].drink<<endl; } */ cout<<maxmatch()<<endl; return 1; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator