| ||||||||||
| 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