程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> HDU 1151 Air Aaid最小路徑覆蓋

HDU 1151 Air Aaid最小路徑覆蓋

編輯:關於C語言

題目大意:
在一個城鎮,有m個路口,和n條路,這些路都是單向的,而且路不會形成環,現在要弄一些傘兵去巡查這個城鎮,
傘兵只能沿著路的方向走,問最少需要多少傘兵才能把所有的路口搜一遍。這個題目就轉換成求解有向無環圖的最
小路徑覆蓋問題了。
一個結論:有向無環圖的最小路徑覆蓋=該圖的頂點數-該圖的最大匹配。
 
AC代碼:
[cpp]
#include<iostream> 
using namespace std; 
 
const int MAX=121; 
int no_of_intersections,no_of_streets,t; 
int link[MAX];    //記錄當前與street終點相連的起點點 
bool map[MAX][MAX];  //存儲二分圖,起點到終點有路徑,則map[x][y]=true;反之,為false 
bool useif[MAX];   //記錄路口點是否使用了) 
 
void getMap()  //存圖 

    memset(map,false,sizeof(map)); 
 
    int a,b; 
    for(int i=1;i<=no_of_streets;i++) 
    { 
        cin>>a>>b; 
        map[a][b]=true; 
    } 

 
bool can(int t) 

    for(int i=1;i<=no_of_intersections;i++) 
    { 
        if(!useif[i] && map[t][i]) 
        { 
            useif[i]=true; 
            if(link[i]==-1 || can(link[i])) 
            { 
                link[i]=t; 
                return true; 
            } 
        } 
    } 
 
    return false; 

 
int maxMatch() 

    int num=0; 
 
    memset(link,int(-1),sizeof(link));  //未連的計為-1 
    for(int i=1;i<=no_of_intersections;i++)   //從street起點開始依次搜索增廣路經 
    { 
        memset(useif,false,sizeof(useif)); 
        if(can(i)) num++; 
    } 
 
    return num; 

 
int main() 

    cin>>t; 
    while(t--) 
    { 
        cin>>no_of_intersections>>no_of_streets; 
 
        getMap(); 
 
        cout<<no_of_intersections-maxMatch()<<endl; 
    } 
 
    return 0; 

 


摘自 ON THE WAY

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved