アットウィキロゴ
yanprog @ ウィキ
アットウィキロゴ
yanprog @ ウィキ
ページ一覧

最大流

最大流

次を貼り付ける。
add_edge(s,t,v)でsからtへ容量vの辺を追加する。
max_flow(s,t)でsからtへの最大流。 

ll INF=1LL<<62-1;
double eps=1e-20;
 
template <typename T> struct cal_max_flow{
	static const int MAX_V=5010;
	struct edge{
		int to;
		T cap;
		int rev;
	};
 
	vector<edge> G[MAX_V];
	int level[MAX_V];
	int iter[MAX_V];
 
	void add_edge(int from,int to,T cap){
		G[from].pb((edge){to,cap,G[to].size()});
		G[to].pb((edge){from,0,G[from].size()-1});
	}
 
	void bfs(int s){
		nclr(level);
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(!que.empty()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>eps && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
 
	T dfs(int v, int t, T f){
		if(v==t){
			return f;
		}
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>eps && level[v]<level[e.to]){
				T d=dfs(e.to, t, min(f,e.cap));
				if(d>eps){
					e.cap-=d;
					G[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
 
	T max_flow(int s,int t){
		T flow=0;
		while(true){
			clr(iter);
			bfs(s);
			if(level[t]<0)return flow;
			T f;
			while( (f=dfs(s,t,INF))>eps){
				flow+=f;
			}
		}
		return flow;
	}
};
 
 
 

使用例１　SRM542 Div1HARD(Rabbit Working) 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define ALL(s) (s).begin(),(s).end
 
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
#define MP(a,b) make_pair((a),(b))
 
using namespace std;
 
// BEGIN CUT HERE
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
os << "[ ";REP(i,z.size())os << z[i] << ", " ;return ( os << "]" << endl);}
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
os << "set( "; EACH(p,z)os << (*p) << ", " ;return ( os << ")" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
os << "{ "; EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;return ( os << "}" << endl);}
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
return ( os << "(" << z.first << ", " << z.second << ",)" );}
// END CUT HERE
 
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<long long> vl;
typedef vector<vector<long long> > vvl;
typedef vector<double> vd;
typedef vector<vector<double> > vvd;
typedef vector<string> vs;
 
 
ll INF=1LL<<62-1;
double eps=1e-20;
 
template <typename T> struct cal_max_flow{
	static const int MAX_V=5010;
	struct edge{
		int to;
		T cap;
		int rev;
	};
 
	vector<edge> G[MAX_V];
	int level[MAX_V];
	int iter[MAX_V];
 
	void add_edge(int from,int to,T cap){
		G[from].pb((edge){to,cap,G[to].size()});
		G[to].pb((edge){from,0,G[from].size()-1});
	}
 
	void bfs(int s){
		nclr(level);
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(!que.empty()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>eps && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
 
	T dfs(int v, int t, T f){
		if(v==t){
			return f;
		}
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>eps && level[v]<level[e.to]){
				T d=dfs(e.to, t, min(f,e.cap));
				if(d>eps){
					e.cap-=d;
					G[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
 
	T max_flow(int s,int t){
		T flow=0;
		while(true){
			clr(iter);
			bfs(s);
			if(level[t]<0)return flow;
			T f;
			while( (f=dfs(s,t,INF))>eps){
				flow+=f;
			}
		}
		return flow;
	}
};
 
int N;
vvi p;
 
 
bool ok(double d){
	cal_max_flow<double> cmf;
	int s=N+N*N;
	int t=s+1;
	REP(i,N){
		cmf.add_edge(s,i,200*d);
	}
	double tot=0.0;
	REP(i,N) REP(j,N){
		if(i>j)continue;
		int v=N+i*N+j;
		cmf.add_edge(i,v,INF);
		cmf.add_edge(j,v,INF);
		double g=p[i][j]+(i==j ? d : 2*d);
		//debug(g);
		cmf.add_edge(v,t,g);
		tot+=g;
	}
	double f=cmf.max_flow(s,t);
	return f+eps<tot;
}
 
class RabbitWorking {
public:
	double getMaximum(vector <string> profit) {
		N=profit.size();
		p=vvi(N,vi(N));
		REP(i,N) REP(j,N) p[i][j]=profit[i][j]-'0';
		double ans=0.0;
		double d=1.0;
		while(ok(d)){
			d*=2;
		}
		while(d>eps){
			if(ok(ans+d))ans+=d;
			d/=2;
		}
		return ans;
	}
};
 

使用例２（最小カットを具体的に求めたい場合は、level[v]が-1かどうか調べる。） graph cut at fuka5 
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <assert.h>
#include <sys/time.h>
#include <fstream>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
 
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define deb(x) cerr << #x << " = " << (x) << " , ";
#define debl cerr << " (L" << __LINE__ << ")"<< endl;
 
 
#define clr(a) memset((a),0,sizeof(a))
#define nclr(a) memset((a),-1,sizeof(a))
#define pb push_back
#define INRANGE(x,s,e) ((s)<=(x) && (x)<(e))
 
double pi=3.14159265358979323846;
 
using namespace std;
static const double EPS = 1e-5;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
 
template<typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& z){
	os << "[ ";
	REP(i,z.size())os << z[i] << ", " ;
	return ( os << "]" << endl);
}
 
template<typename T> std::ostream& operator<<(std::ostream& os, const set<T>& z){
	os << "set( "; 
	EACH(p,z)os << (*p) << ", " ;
	return ( os << ")" << endl);
}
 
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const map<T,U>& z){
	os << "{ "; 
	EACH(p,z)os << (p->first) << ": " << (p->second) << ", " ;
	return ( os << "}" << endl);
}
 
template<typename T,typename U> std::ostream& operator<<(std::ostream& os, const pair<T,U>& z){
	return ( os << "(" << z.first << ", " << z.second << ",)" );
}
 
double get_time(){
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec*1e-6;
}
 
ll INF=1LL<<62-1;
double eps=1e-20;
 
template <typename T> struct cal_max_flow{
	static const int MAX_V=5010;
	struct edge{
		int to;
		T cap;
		int rev;
	};
 
	vector<edge> G[MAX_V];
	int level[MAX_V];
	int iter[MAX_V];
 
	void add_edge(int from,int to,T cap){
		G[from].pb((edge){to,cap,G[to].size()});
		G[to].pb((edge){from,0,G[from].size()-1});
	}
 
	void bfs(int s){
		nclr(level);
		queue<int> que;
		level[s]=0;
		que.push(s);
		while(!que.empty()){
			int v=que.front();
			que.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>eps && level[e.to]<0){
					level[e.to]=level[v]+1;
					que.push(e.to);
				}
			}
		}
	}
 
	T dfs(int v, int t, T f){
		if(v==t){
			return f;
		}
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(e.cap>eps && level[v]<level[e.to]){
				T d=dfs(e.to, t, min(f,e.cap));
				if(d>eps){
					e.cap-=d;
					G[e.to][e.rev].cap+=d;
					return d;
				}
			}
		}
		return 0;
	}
 
	T max_flow(int s,int t){
		T flow=0;
		while(true){
			clr(iter);
			bfs(s);
			if(level[t]<0)return flow;
			T f;
			while( (f=dfs(s,t,INF))>eps){
				flow+=f;
			}
		}
		return flow;
	}
};
 
void _main(istream &inp){
	while(true){
		int w,h;
		double _r,_k;
		inp >> h >> w >> _r >> _k >> ws;
		if(h==0)break;
		int r=_r*1000+0.5;
		int k=_k*1000+0.5;
		ll big=1LL<<33;
		vector<string> a1;
		REP(i,h){
			string u;
			inp >> u;
			a1.pb(u);
		}
		int s=w*h, t=w*h+1;
		cal_max_flow<ll> cmf;
		REP(x,h) REP(y,w){
			int p=x*w+y;
			if(a1[x][y]=='#'){
				cmf.add_edge(s,p,r+big);
				cmf.add_edge(p,t,big);
			}
			else if(a1[x][y]=='.'){
				cmf.add_edge(s,p,big);
				cmf.add_edge(p,t,r+big);
			}
			else{
				assert(false);
			}
		}
		REP(x1,h) REP(y1,w) REP(x2,h) REP(y2,w){
			int p=x1*w+y1;
			int p2=x2*w+y2;
			if(abs(x1-x2)+abs(y1-y2)==1)cmf.add_edge(p,p2,k);
		}
		ll d=cmf.max_flow(s,t);
		d-=big*w*h;
		cmf.bfs(s);
		vector<string> a2(h, string(w,'.'));
		REP(x,h) REP(y,w) if(cmf.level[x*w+y]!=-1)a2[x][y]='#';
		cout << 0.001*d << endl;
		REP(i,a2.size()) cout << a2[i] << endl;
 
	}
}
 
int main(){
	if(1){
		ifstream ifs("test.txt");
		_main(ifs);
	}
	else{
		_main(cin);
	}
	return 0;
}
 

タグ：

+ タグ編集
  • タグ：
タグの更新に失敗しました
エラーが発生しました。ページを更新してください。
ページを更新
「最大流」をウィキ内検索
最終更新：2012年06月01日 22:34