学步园

HDU 1150:

http://acm.hdu.edu.cn/showproblem.php?pid=1150

      两台机器，有n和m个工作模式，起始工作模式都为0，现在有k件工作，第i件工作可分别在两个机器上用各自的模式工作，但换模式要重启，问重启的最小次数。

      写的时候因为是找二分最大匹配的题目时找到写的，想到了二分上去，也知道是求最小覆盖点 == 最大匹配数，但不是很能理解，先把代码写了再说。

      写的时候注意起始模式是0，所以换模式时把0的排除再外。（因为这个原因错了很多次）

一：邻接阵做法

#include<iostream><br /> using namespace std;</p> <p>int n,m,k;<br /> int map[105][105]; //记录X,Y对应点可否连接<br /> int vis[105]; //每次找增广路时对Y中点是否访问<br /> int dir[105]; //Y中点匹配的X中点的位置</p> <p>int find(int a)<br /> {<br /> int i;<br /> for(i=0;i<m;i++)<br /> {<br /> if(map[a][i]==1 && vis[i] == 0)<br /> {<br /> vis[i] = 1;<br /> if(dir[i] == -1 || find(dir[i]))<br /> {<br /> dir[i] = a;<br /> return 1;<br /> }<br /> }<br /> }<br /> return 0;<br /> }</p> <p>int main()<br /> {<br /> int i,x,y;<br /> while(scanf("%d",&n)!=EOF && n!=0)<br /> {<br /> memset(map,0,sizeof(map));<br /> memset(dir,-1,sizeof(dir));<br /> scanf("%d%d",&m,&k);<br /> while(k--)<br /> {<br /> scanf("%d%d%d",&i,&x,&y);<br /> if(x && y)<br /> map[x][y] = 1; //应该不能再用map[y][x] = 1<br /> }<br /> int sum = 0;<br /> for(i=0;i<n;i++)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> if(find(i))<br /> sum++;<br /> }</p> <p> printf("%d/n",sum);<br /> }<br /> return 0;<br /> }

二：动态邻接表做法.

#include<iostream><br /> using namespace std;</p> <p>int n,m,k;<br /> int vis[105]; //每次找增广路时对Y中点是否访问<br /> int dir[105]; //Y中点匹配的X中点的位置</p> <p>struct edge<br /> {<br /> int from;<br /> int to;<br /> edge* next;<br /> edge()<br /> {<br /> from = to = 0;<br /> next = NULL;<br /> }<br /> };<br /> edge* List[105];</p> <p>void add_edge(int f,int t)<br /> {<br /> edge* node = new edge();<br /> node->from = f;<br /> node->to = t;<br /> node->next = List[f];<br /> List[f] = node;<br /> }</p> <p>int find(edge* node)<br /> {<br /> while(1)<br /> {<br /> if(node == NULL)<br /> {<br /> break;<br /> }<br /> int i = node->to;<br /> if(vis[i] == 0)<br /> {<br /> vis[i] = 1;<br /> if(dir[i] == -1 || find(List[dir[i]]))<br /> {<br /> dir[i] = node->from;<br /> return 1;<br /> }<br /> }<br /> node = node->next;<br /> }<br /> return 0;<br /> }</p> <p>int main()<br /> {<br /> int i,x,y;<br /> while(scanf("%d",&n)!=EOF && n!=0)<br /> {<br /> for(i=0;i<=n;i++)//链表清空，一开始没清空，错了很多次<br /> {<br /> List[i] = NULL;<br /> }<br /> memset(dir,-1,sizeof(dir));<br /> scanf("%d%d",&m,&k);<br /> while(k--)<br /> {<br /> scanf("%d%d%d",&i,&x,&y);<br /> if(x && y)<br /> add_edge(x,y);<br /> }<br /> int sum = 0;<br /> for(i=1;i<=n;i++)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> if(find(List[i]))<br /> sum++;<br /> }<br /> printf("%d/n",sum);<br /> }<br /> return 0;<br /> }

三：静态邻接表做法

HDU 1151:

http://acm.hdu.edu.cn/showproblem.php?pid=1151

     最小路径覆盖（选取最少的边覆盖所有的点） == 节点数 - 最大匹配数

#include <iostream><br /> using namespace std;<br /> #define MAXN 125</p> <p>int vis[MAXN];<br /> int link[MAXN];<br /> int n,m;</p> <p>struct edge<br /> {<br /> int from;<br /> int to;<br /> edge* next;<br /> edge()<br /> {<br /> from = to = 0;<br /> next = NULL;<br /> }<br /> };<br /> edge* List[MAXN];</p> <p>void add_edge(int f,int t)<br /> {<br /> edge* node = new edge();<br /> node->from = f;<br /> node->to = t;<br /> node->next = List[f];<br /> List[f] = node;<br /> }</p> <p>bool find(edge* node)<br /> {<br /> while(1)<br /> {<br /> if(node == NULL)<br /> break;<br /> int i = node->to;<br /> if(vis[i] == 0)<br /> {<br /> vis[i] = 1;<br /> if(link[i] == 0 || find(List[link[i]]))<br /> {<br /> link[i] = node->from;<br /> return 1;<br /> }<br /> }<br /> node = node->next;<br /> }</p> <p> return 0;<br /> }</p> <p>int main()<br /> {<br /> int i;<br /> int t,x,y;<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> memset(link,0,sizeof(link));<br /> scanf("%d%d",&n,&m);<br /> for(i=0;i<=n;i++)<br /> {<br /> List[i] = NULL;<br /> }<br /> for(i=0;i<m;i++)<br /> {<br /> scanf("%d%d",&x,&y);<br /> add_edge(x,y);<br /> }<br /> int sum = 0;<br /> for(i=1;i<=n;i++)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> if(find(List[i]))<br /> sum++;<br /> }</p> <p> printf("%d/n",n-sum);<br /> }<br /> return 0;<br /> }

HDU 1068:

HDU 1281:

HDU 1498:

HDU 1528:

HDU 1501:

POJ 2724:

POJ 3216:

POJ 2239:

一道如此简单的题目我竟然连续犯了好几个错误：

1：一开始对Y数组开太小，RE；

2：忘了对邻接表进行清理；

3：算Y数组时算错。

#include <iostream><br /> using namespace std;<br /> #define num_1 305<br /> #define num_2 100</p> <p>int n;<br /> bool vis[num_2];<br /> int dir[num_2];</p> <p>struct edge<br /> {<br /> int from;<br /> int to;<br /> edge* next;<br /> edge()<br /> {<br /> from = to = 0;<br /> next = NULL;<br /> }<br /> };<br /> edge* T[num_1];</p> <p>void add_edge(int f,int t)<br /> {<br /> edge *node = new edge();<br /> node->to = t;<br /> node->from = f;<br /> node->next = T[f];<br /> T[f] = node;<br /> }</p> <p>bool find(edge* node)<br /> {<br /> while(node != NULL)<br /> {<br /> int i = node->to;<br /> if(vis[i] == 0)<br /> {<br /> vis[i] = 1;<br /> if( dir[i] == -1 || find( T[dir[i]] ) )<br /> {<br /> dir[i] = node->from;<br /> return true;<br /> }<br /> }</p> <p> node = node->next;<br /> }</p> <p> return false;<br /> }</p> <p>int solve()<br /> {<br /> int res = 0;<br /> int i;<br /> memset(dir,-1,sizeof(dir));<br /> for(i=1;i<=n;i++)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> if(find(T[i]))<br /> res++;<br /> }</p> <p> return res;<br /> }</p> <p>void Init()<br /> {<br /> int t,p,q;<br /> int i;<br /> for(i=1;i<=n;i++)<br /> {<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> scanf("%d%d",&p,&q);<br /> add_edge(i,(p-1)*12+q);<br /> }<br /> }<br /> }</p> <p>void clean()<br /> {<br /> int i;<br /> for(i=0;i<=n;i++)<br /> T[i] = NULL;<br /> }</p> <p>int main()<br /> {<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> Init();<br /> int num = solve();<br /> printf("%d/n",num);<br /> clean(); //老是忘掉<br /> }<br /> return 0;<br /> }

POJ 2584:

一道水题，就是建图的时候比较麻烦，仔细想一下已可以很顺利出来。1Y。

#include <iostream><br /> #include <string><br /> using namespace std;<br /> #define num_1 25<br /> #define num_2 105</p> <p>int n;<br /> string str;<br /> bool vis[num_2];<br /> int dir[num_2];<br /> bool map[25][6];</p> <p>struct edge<br /> {<br /> int from;<br /> int to;<br /> edge* next;<br /> edge()<br /> {<br /> from = to = 0;<br /> next = NULL;<br /> }<br /> };<br /> edge* T[num_1];</p> <p>void add_edge(int f,int t)<br /> {<br /> edge *node = new edge();<br /> node->to = t;<br /> node->from = f;<br /> node->next = T[f];<br /> T[f] = node;<br /> }</p> <p>bool find(edge* node)<br /> {<br /> while(node != NULL)<br /> {<br /> int i = node->to;<br /> if(vis[i] == 0)<br /> {<br /> vis[i] = 1;<br /> if( dir[i] == -1 || find( T[dir[i]] ) )<br /> {<br /> dir[i] = node->from;<br /> return true;<br /> }<br /> }</p> <p> node = node->next;<br /> }</p> <p> return false;<br /> }</p> <p>int solve()<br /> {<br /> int res = 0;<br /> int i;<br /> memset(dir,-1,sizeof(dir));<br /> for(i=1;i<=n;i++)<br /> {<br /> memset(vis,0,sizeof(vis));<br /> if(find(T[i]))<br /> res++;<br /> }</p> <p> return res;<br /> }</p> <p>void Init()<br /> {<br /> int i,j,k;<br /> char s,e;<br /> int start,end;</p> <p> memset(map,0,sizeof(map));</p> <p> scanf("%d",&n);</p> <p> for(i=1;i<=n;i++)<br /> {<br /> cin>>s>>e;<br /> switch(s)<br /> {<br /> case 'S':start = 1;break;<br /> case 'M':start = 2;break;<br /> case 'L':start = 3;break;<br /> case 'X':start = 4;break;<br /> case 'T':start = 5;break;<br /> }<br /> switch(e)<br /> {<br /> case 'S':end = 1;break;<br /> case 'M':end = 2;break;<br /> case 'L':end = 3;break;<br /> case 'X':end = 4;break;<br /> case 'T':end = 5;break;<br /> }<br /> for(j=start;j<=end;j++)<br /> {<br /> map[i][j] = 1;<br /> }<br /> }<br /> for(i=1;i<=5;i++)<br /> {<br /> int num;<br /> scanf("%d",&num);</p> <p> int count = 1;<br /> for(j=1;j<=n;j++)<br /> {<br /> if(map[j][i] == 1)<br /> {<br /> for(k=1;k<=num;k++)<br /> add_edge(j,(i-1)*20+k);<br /> }<br /> }</p> <p> }</p> <p> cin>>str;<br /> }</p> <p>void clean()<br /> {<br /> int i;<br /> for(i=0;i<num_1;i++)<br /> T[i] = NULL;<br /> }</p> <p>int main()<br /> {<br /> while(1)<br /> {<br /> cin>>str;<br /> if(str == "ENDOFINPUT")<br /> break;</p> <p> Init();</p> <p> int num = solve();<br /> if(num == n)<br /> printf("T-shirts rock!/n");<br /> else<br /> printf("I'd rather not wear a shirt anyway.../n");</p> <p> clean(); //老是忘掉<br /> }<br /> return 0;<br /> }

POJ 1422:

POJ 1325:

POJ 1719:

POJ 2594:

POJ 2195:

POJ 2446:

POJ 1904:

POJ 3342:

POJ 3216:

POJ 3020: