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 |
100题留纪念 map记得清零还算比较容易啦 map忘记清零WA #include <iostream> using namespace std; #define SIZE 2000 #define COUR 300 bool chk[SIZE];//相当于check int match[SIZE]; int map[SIZE][SIZE]; int n,m;//左边的点的个数 右边的点的个数 int dfs(int p)//P点进行查找,找到则增广 { int i,t; for(i=1+COUR;i<=127+COUR;i++)//需要配置!! if(map[p][i] && !chk[i])//找p的一个对应点且该店没有检查过(尝试更新i的匹配) { chk[i]=1; t=match[i]; match[i]=p; if(t==-1 || dfs(t))//如果t是一个初始值,表示i点原来没有匹配,则增广成功返回或者特点能重新找到一个新的匹配点 return 1; match[i]=t;//不成立则改回来哦亲 } return 0; } void Pro() { int i,res=0; memset(match,-1,sizeof(match)); for(i=1;i<=n;i++) //需要配置!! { memset(chk,0,sizeof(chk)); res+=dfs(i); } cout<<res<<endl; } /* 模板参数配置: n:左边点的个数 m右边点的个数 l:13、27的结束范围 */ int main() { freopen("in.txt","r",stdin); int i,j,k,a,b; while(scanf("%d",&n)!=EOF) { memset(map,0,sizeof(map)); for(i=1;i<=n;i++) { scanf("%d",&j); while(j--) { scanf("%d%d",&a,&b); b*=10; b+=a; b+=COUR; map[i][b]=1; map[b][i]=1; } } Pro(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator