アルゴリズム導論26(最大ストリーム)
6109 ワード
26.1ストリーミングネットワーク
26.2 Ford-Fulkersonメソッド
Edmonds-Karpアルゴリズム
26.3最大二分整合
Hungaryアルゴリズム
「点Aからの広がり経路」は、点Aに一致しない点Bに必ず接続される.点Bが何の点にも一致していない場合、それはこの拡張経路の終点である.逆に、点Bが点Cと一致する場合、この広がり経路は点Aから点B、点Bから点C、さらに「点Cからの広がり経路」であり、この「点Cからの広がり経路」は、前の広がり経路上の既存の点を含んではならない.
26.2 Ford-Fulkersonメソッド
Edmonds-Karpアルゴリズム
#include<iostream>
#include<queue>
using namespace std;
#define n 20
int f[n][n],cf[n][n],pred[n];
bool visited[n];
typedef struct
{
int VNum,ENum;
int w[n][n];
}Graph;
void create_graph(Graph &G)
{
int i,j,v1,v2;
cin>>G.VNum>>G.ENum;
for(i=0;i<G.VNum;i++)
{
for(j=0;j<G.VNum;j++)G.w[i][j]=0;
}
for(i=0;i<G.ENum;i++)
{
cin>>v1>>v2>>j;
G.w[v1][v2]=j;
}
}
bool Edmonds_Karp(Graph G,int s,int t)
{
int i,j;
for(i=0;i<G.VNum;i++)
{
for(j=0;j<G.VNum;j++)
{
if(G.w[i][j]>0)cf[i][j]=G.w[i][j]-f[i][j];
else if(G.w[j][i]>0)cf[i][j]=f[j][i];
else cf[i][j]=0;
}
}
for(i=0;i<G.VNum;i++)visited[i]=false;
queue<int>q;
visited[s]=true;
q.push(s);
while(!q.empty())
{
i=q.front();
q.pop();
for(j=0;j<G.VNum;j++)
{
if(!visited[j]&&cf[i][j])
{
visited[j]=true;
q.push(j);
pred[j]=i;
if(j==t)return true;
}
}
}
return false;
}
int Ford_Fulkerson(Graph G,int s,int t)
{
int i,j,min=10000,total=0;
for(i=0;i<G.VNum;i++)
{
for(j=0;j<G.VNum;j++)
{
if(G.w[i][j]>0)f[i][j]=0;
}
}
while(Edmonds_Karp(G,s,t))
{
i=t;
while(i!=s)
{
if(cf[pred[i]][i]<min)min=cf[pred[i]][i];
i=pred[i];
}
i=t;
while(i!=s)
{
if(G.w[pred[i]][i]>0)f[pred[i]][i]+=min;
else f[i][pred[i]]-=min;
i=pred[i];
}
total+=min;
}
return total;
}
int main()
{
Graph G;
create_graph(G);
cout<<Ford_Fulkerson(G,0,5)<<endl;
for(int i=0;i<G.VNum;i++)
{
for(int j=0;j<G.VNum;j++)
{
if(G.w[i][j]>0)cout<<f[i][j]<<' ';
else cout<<0<<' ';
}
cout<<endl;
}
return 0;
}
26.3最大二分整合
Hungaryアルゴリズム
「点Aからの広がり経路」は、点Aに一致しない点Bに必ず接続される.点Bが何の点にも一致していない場合、それはこの拡張経路の終点である.逆に、点Bが点Cと一致する場合、この広がり経路は点Aから点B、点Bから点C、さらに「点Cからの広がり経路」であり、この「点Cからの広がり経路」は、前の広がり経路上の既存の点を含んではならない.
#include<iostream>
using namespace std;
#define N 20
bool visited[N];
int map[N][N],match[N],m,n;
bool find(int x)
{
int i;
for(i=0;i<n;i++)
{
if(!visited[i]&&map[x][i])
{
visited[i]=true;
if(match[i]==-1||find(match[i]))
{
match[i]=x;
return true;
}
}
}
return false;
}
int Hungary()
{
int i,num=0;
for(i=0;i<m;i++)
{
memset(visited,false,sizeof(visited));
if(find(i))num++;
}
return num;
}
int main()
{
int i,j,k,edge;
cin>>m>>n>>edge;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)map[i][j]=0;
}
for(i=0;i<edge;i++)
{
cin>>j>>k;
map[j][k]=1;
}
memset(match,-1,sizeof(match));
cout<<Hungary()<<endl;
return 0;
}
POJ1469
#include<iostream> using namespace std; #define max 20 int map[max][max],match[max],P,N; bool visited[max]; bool find(int x) { int i; for(i=0;i<P;i++) { if(!visited[i]&&map[x][i]) { visited[i]=true; if(match[i]==-1||find(match[i])) { match[i]=x; return true; } } } return false; } int Hungary() { int i,num=0; for(i=0;i<N;i++) { memset(visited,false,sizeof(visited)); if(find(i))num++; } return num; } int main() { int t,num,i,j; scanf("%d",&t); while(t--) { scanf("%d%d",&P,&N); if(P<N)printf("%s
","NO"); else { memset(map,0,sizeof(map)); memset(match,-1,sizeof(match)); for(i=0;i<P;i++) { scanf("%d",&num); while(num--) { scanf("%d",&j); map[i][j-1]=1; } } printf("%s
",Hungary()==P?"YES":"NO"); } } return 0; }
POJ3041#include<iostream> using namespace std; #define max 20 int map[max][max],match[max],m; bool visited[max]; bool find(int x) { int i; for(i=0;i<m;i++) { if(!visited[i]&&map[x][i]) { visited[i]=true; if(match[i]==-1||find(match[i])) { match[i]=x; return true; } } } return false; } int Hungary() { int i,num=0; for(i=0;i<m;i++) { memset(visited,false,sizeof(visited)); if(find(i))num++; } return num; } int main() { int num,i,j; scanf("%d%d",&m,&num); memset(map,0,sizeof(map)); memset(match,-1,sizeof(match)); while(num--) { scanf("%d%d",&i,&j); map[i-1][j-1]=1; } printf("%d
",Hungary()); return 0; }