#include <iostream>
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
int n,s,t,c,mf,f;
vector<vector<int> > res;
vector<int> p;
void augment(int u,int flow){
if(u==s){
f=flow;
return;
}
if(p[u]==-1)
return;
augment(p[u],min(flow,res[p[u]][u]));
res[p[u]][u]-=f;
res[u][p[u]]+=f;
}
int main(){
int net=1;
while(1){
cin>>n;
if(!n){
// cout<<endl;
return 0;
}
cin>>s>>t>>c;
mf=0;
res.assign(n+1,vector<int>(n+1,0));
for(int i=0;i<c;i++){
int x,y,w;
cin>>x>>y>>w;
res[x][y]+=w,res[y][x]+=w;
}
while(1){
f=0;
p.assign(n+1,-1);
p[s]=s;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
if(u==t)
break;
for(int i=1;i<=n;i++){
if(res[u][i]>0&&p[i]==-1)
q.push(i),p[i]=u;
}
}
augment(t,1001);
if(!f)
break;
mf+=f;
}
cout<<"Network "<<net++<<endl;
cout<<"The bandwidth is "<<mf<<'.'<<endl<<endl;
}
return 0;
}
#include <vector>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <utility>
typedef unsigned long long ull;
using namespace std;
int n,s,t,c,mf,f;
vector<vector<int> > res;
vector<int> p;
void augment(int u,int flow){
if(u==s){
f=flow;
return;
}
if(p[u]==-1)
return;
augment(p[u],min(flow,res[p[u]][u]));
res[p[u]][u]-=f;
res[u][p[u]]+=f;
}
int main(){
int net=1;
while(1){
cin>>n;
if(!n){
// cout<<endl;
return 0;
}
cin>>s>>t>>c;
mf=0;
res.assign(n+1,vector<int>(n+1,0));
for(int i=0;i<c;i++){
int x,y,w;
cin>>x>>y>>w;
res[x][y]+=w,res[y][x]+=w;
}
while(1){
f=0;
p.assign(n+1,-1);
p[s]=s;
queue<int> q;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
if(u==t)
break;
for(int i=1;i<=n;i++){
if(res[u][i]>0&&p[i]==-1)
q.push(i),p[i]=u;
}
}
augment(t,1001);
if(!f)
break;
mf+=f;
}
cout<<"Network "<<net++<<endl;
cout<<"The bandwidth is "<<mf<<'.'<<endl<<endl;
}
return 0;
}
Comments
Post a Comment