POJ 2594 二分圖最小路徑覆蓋
題意：將所有點都連起來至少需要多少條路徑
思路：二分圖的最小路徑覆蓋，而最小路徑覆==圖的頂點數-圖的最大匹配，而當初還學習過最小頂點覆蓋==最大匹配，而最小頂點覆蓋需要連雙向邊，結果除以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
