題意：
? ? ? 題意就是給你個(gè)有向無(wú)環(huán)圖，問(wèn)你最少放多少個(gè)機(jī)器人能把圖全部遍歷，機(jī)器人不能走回頭路線。


思路：

? ? ?如果直接建圖，跑一遍二分匹配輸出n - 最大匹配數(shù)會(huì)跪，原因是這個(gè)題目和以往見(jiàn)到的題目不一樣的，區(qū)別就在，之前很多題目給的都是全邊，就是假如 a->b b->c ，那么他一定會(huì)給你一條 a->c，因?yàn)閍->c也是有指向關(guān)系的，而這個(gè)題目就沒(méi)有給a->c，這就需要我們自己去找到所有可達(dá)邊，一遍Floyd或者深搜都行，深搜是O(n^2)的，會(huì)快一點(diǎn)。給你在網(wǎng)上找的例子。

#include<stdio.h> #include<string.h>#define N_node 510 #define N_edge 300000 #define INF 100000000typedef struct {int to ,next; }STAR;STAR E[N_edge]; int list[N_node] ,tot; int mk_dfs[N_node] ,mk_gx[N_node]; int map[510][510];void add(int a ,int b) {E[++tot].to = b;E[tot].next = list[a];list[a] = tot; }int DFS_XYL(int x) {for(int k = list[x] ;k ;k = E[k].next){int to = E[k].to;if(mk_dfs[to]) continue;mk_dfs[to] = 1;if(mk_gx[to] == -1 || DFS_XYL(mk_gx[to])){mk_gx[to] = x;return 1;}}return 0; }int minn(int x ,int y) {return x < y ? x : y; }void Floyd(int n) {for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)for(int j = 1 ;j <= n ;j ++)map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]); }int main () {int n ,m ,i ,j;int a ,b;while(~scanf("%d %d" ,&n ,&m) && n + m){for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= n ;j ++)if(i == j) map[i][j] = 0;else map[i][j] = INF;for(i = 1 ;i <= m ;i ++){scanf("%d %d" ,&a ,&b);map[a][b] = 1;}Floyd(n);memset(list ,0 ,sizeof(list));tot = 1;for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= n ;j ++){if(i == j || map[i][j] == INF) continue;add(i ,j);}int sum = 0;memset(mk_gx ,255 ,sizeof(mk_gx));for(i = 1 ;i <= n ;i ++){memset(mk_dfs ,0 ,sizeof(mk_dfs));sum += DFS_XYL(i);}printf("%d\n" ,n - sum);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的POJ2594 最小路径覆盖的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。