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

POJ 2594 二分圖最小路徑覆蓋

編輯:關於C++

題意:將所有點都連起來至少需要多少條路徑

思路:二分圖的最小路徑覆蓋,而最小路徑覆==圖的頂點數-圖的最大匹配,而當初還學習過最小頂點覆蓋==最大匹配,而最小頂點覆蓋需要連雙向邊,結果除以2,那是因為1-->2時,點1和點2都已經用過,所以我在連一個相應的一條邊,代表這兩個點不能在用了,樣例詳見hdu 1054 第二組。而接下來的求最小路徑覆蓋的最大匹配我們就只能是單向的,這個為什麼可以避免呢,因為1-->2-->3這樣的話,最小路徑為1,但是轉化為二分圖上的話,對應的點2就可以用兩次,但也只能用兩次,左邊一次,右邊一次,這樣就滿足了1--->2-->3的條件,最小路徑覆蓋可以這樣理解,若沒有邊相連的n個點,最小路徑覆蓋就為n,多一條邊就少一條路徑,最後最大匹配即為多的邊數,減去就是結果,沒有匹配的點也可以直接理解為孤立點........但是這道題的每個點可以走多次,那麼如果1-->2-->3我就可以從1到2,又可以從1直接到3,用floyd判斷點是否可以到達,然後連邊求最小路徑覆蓋就行了

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=1010;
struct edge{
    int to,cap,rev;
    edge(){}
    edge(int a,int b,int c){to=a;cap=b;rev=c;}
};
vector G[maxn];
int level[maxn],iter[maxn];
void addedge(int from,int to,int cap){
    G[from].push_back(edge(to,cap,G[to].size()));
    G[to].push_back(edge(from,0,G[from].size()-1));
}
void bfs(int s){
    memset(level,-1,sizeof(level));
    queueque;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int v=que.front();que.pop();
        for(unsigned int i=0;i0&&level[e.to]<0){
                level[e.to]=level[v]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f){
    if(v==t) return f;
    for(int &i=iter[v];i0&&level[v]0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int max_flow(int s,int t){
    int flow=0;
    while(1){
        bfs(s);
        if(level[t]<0) return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while((f=dfs(s,t,inf))>0) flow+=f;
    }
}
int num[510][510];
void floyd(int V){
    for(int k=1;k<=V;k++){
        for(int i=1;i<=V;i++){
            for(int j=1;j<=V;j++)
                num[i][j]=min(num[i][j],num[i][k]+num[k][j]);
        }
    }
}
int main(){
    int n,m,a,b;
    while(scanf("%d%d",&n,&m)!=-1){
        if(n==0&&m==0) break;
        memset(num,inf,sizeof(num));
        for(int i=0;i
   
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved