胶州网站建设案例,一个网站怎么做软件好用,wordpress主题解锁,在线制作论坛网站题目链接#xff1a;http://acm.hdu.edu.cn/showproblem.php?pid2444思路#xff1a;首先要判断能否构成二分图#xff0c;用bfs对当前点u染色#xff0c;对u的邻接点v的颜色进行判断#xff0c;如果为染色#xff0c;则染色后入队列#xff0c;否则#xff0c;判断co…题目链接http://acm.hdu.edu.cn/showproblem.php?pid2444思路首先要判断能否构成二分图用bfs对当前点u染色对u的邻接点v的颜色进行判断如果为染色则染色后入队列否则判断color[v]color[u],如果相等说明无法构成二部图 直接返回false即可。最后就是简单的匈牙利直接求最大匹配就可以了不过这儿是无向图最后要除以2。 1 #includeiostream2 #includecstdio3 #includecstring4 #includealgorithm5 #includequeue6 #includevector7 using namespace std;8 #define MAXN 2229 vectorintvet[MAXN];
10 int color[MAXN];
11 bool mark[MAXN];
12 int match[MAXN];
13 int n,m;
14
15 bool bfs(){
16 queueintQ;
17 Q.push(1);mark[1]true;
18 while(!Q.empty()){
19 int uQ.front();
20 Q.pop();
21 int ccolor[u];
22 for(int i0;ivet[u].size();i){
23 int vvet[u][i];
24 if(!mark[v]){ mark[v]true;color[v]-c;Q.push(v); }
25 else if(color[v]c)return false;
26 }
27 }
28 return true;
29 }
30
31 bool dfs(int u){
32 for(int i0;ivet[u].size();i){
33 int vvet[u][i];
34 if(!mark[v]){
35 mark[v]true;
36 if(match[v]-1||dfs(match[v])){
37 match[v]u;
38 return true;
39 }
40 }
41 }
42 return false;
43 }
44
45
46 int MaxMatch(){
47 int res0;
48 memset(match,-1,sizeof(match));
49 for(int i1;in;i){
50 memset(mark,false,sizeof(mark));
51 resdfs(i);
52 }
53 return res;
54 }
55
56
57 int main(){
58 // freopen(1.txt,r,stdin);
59 int u,v;
60 while(~scanf(%d%d,n,m)){
61 for(int i1;in;i)vet[i].clear();
62 for(int i1;im;i){
63 scanf(%d%d,u,v);
64 vet[u].push_back(v);
65 vet[v].push_back(u);
66 }
67 memset(color,-1,sizeof(color));
68 memset(mark,false,sizeof(mark));
69 if(!bfs()){ puts(No);continue; }
70 int ansMaxMatch();
71 printf(%d\n,ans/2);
72 }
73 return 0;
74 } View Code 转载于:https://www.cnblogs.com/wally/archive/2013/06/03/3116104.html
