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