2014-03-23

3169:Layout

POJ グラフ

蟻本で解説されてる問題。やっと理解した。

不等式制約の双対をとると最短経路問題になる。

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_V 1001
#define MAX_E 30000
#define INF (1<<29)

using namespace std;

struct edge{int from,to,cost;};

vector<edge> es;

int d[MAX_V],n;

void shortest_path(int s){
	for(int i=0;i<n;i++)d[i]=INF;
	d[s]=0;
	for(int k=0;k<n;k++){
		bool update=false;
		for(int i=0;i<es.size();i++){
			edge e=es[i];
			if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost){
				d[e.to]=d[e.from]+e.cost;
				update=true;
			}
		}
		if(!update)break;
	}
}

int main(void){

	int ml,md;
	cin >> n >> ml >> md;

	for(int i=0;i<n-1;i++){
		es.push_back((edge){i+1,i,0});
	}

	for(int i=0;i<ml;i++){
		int a,b,d;
		cin >> a >> b >> d;
		es.push_back((edge){a-1,b-1,d});
	}

	for(int i=0;i<md;i++){
		int a,b,d;
		cin >> a >> b >> d;
		es.push_back((edge){b-1,a-1,-d});
	}

	shortest_path(0);

	if(d[n-1]==INF)cout << -2 << endl;
	else if(d[0]<0)cout << -1 << endl;
	else cout << d[n-1] << endl;

	return 0;
}

2014-03-22

2455:Secret Milking Machine

POJ フロー

問題文
http://poj.org/problem?id=2455

1~Nの頂点があって、1からNの間をT回移動したい。
一度移動に使った辺は使用できない。
移動の時に使う辺のコストの最大値を最小化せよ。

二分探索+最大流。
二分探索で、移動に使用する辺の最大値を決め打ちする。
決めた値以下の辺のみでグラフを作る。容量は全て1。
このグラフで1からNへT以上流すことができたらその値で可能。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>

#define MAX_V 201
#define INF (1LL<<60)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

struct edge{ll to,cap,rev;};

vector<edge> G[MAX_V];

void add_edge(ll from,ll to,ll cap){
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}

ll level[MAX_V],iter[MAX_V];

ll bfs(ll s){
	memset(level, -1, sizeof(level));
	queue<ll>que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		ll v=que.front();
		que.pop();
		int sz=G[v].size();
		for(int i=0;i<sz;i++){
			edge &e=G[v][i];
			if(e.cap>0 && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}

ll dfs(ll v,ll t,ll f){
	if(v==t)return f;
	int sz=G[v].size();
	for(ll &i=iter[v];i<sz;i++){
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to]){
			ll d=dfs(e.to,t,min(e.cap,f));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

ll max_flow(ll s,ll t){
	ll flow=0;
	for(;;){
		bfs(s);
		if(level[t]<0)return flow;
		memset(iter, 0, sizeof(iter));
		ll f;
		while((f=dfs(s,t,INF))>0)flow+=f;
	}
}

int main(void){

	ll n,p,t;
	cin >> n >> p >> t;

	ll from[p],to[p],cost[p],mx=0;

	for(int i=0;i<p;i++){
		scanf("%lld %lld %lld",&from[i],&to[i],&cost[i]);
		from[i]--,to[i]--;
		mx=max(mx,cost[i]);
	}

	ll l=0,r=mx+1;
	while(r-l>1){
		ll m=(l+r)/2;

		for(int i=0;i<n;i++)G[i].clear();

		for(int i=0;i<p;i++){
			if(cost[i]<=m){
				add_edge(from[i],to[i],1LL);
				add_edge(to[i],from[i],1LL);
			}
		}
		if(max_flow(0,n-1)>=t)r=m;
		else l=m;
	}

	cout << r << endl;

	return 0;
}

2014-03-21

2391:Ombrophobic Bovines

POJ フロー

問題文
http://poj.org/problem?id=2391

n頭の牛とm個のフィールドがある。
フィールドにはそれぞれ小屋があり、入れる牛の数も決まっている。
また、フィールド同士は辺でつながっている。
辺には牛が通れる数の制限はない。
全ての牛が小屋に入ることを考える。
最後に小屋に入る牛の小屋に入るまでの時間を最小化せよ。

二分探索+最大流。
牛が通れる数を容量とした2部グラフをつくる。
このとき、二分探索で求めたい時間を決め打ちして、その時間より大きい辺は使わないようにする。
このグラフでの最大流が牛の数と一致していれば、その時間ですべての牛を小屋に入れることができる。

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <cstring>
#define MAX_V 405
#define INF (1LL<<60)

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;

struct edge{ll to,cap,rev;};

vector<edge>G[MAX_V];

inline void add_edge(ll from,ll to,ll cap){
	G[from].push_back((edge){to,cap,G[to].size()});
	G[to].push_back((edge){from,0,G[from].size()-1});
}

ll level[MAX_V],iter[MAX_V];

inline ll bfs(ll s){
	memset(level, -1, sizeof(level));
	queue<ll>que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		ll v=que.front();
		que.pop();
		int sz=G[v].size();
		for(int i=0;i<sz;i++){
			edge &e=G[v][i];
			if(e.cap>0 && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}

inline ll dfs(ll v,ll t,ll f){
	if(v==t)return f;
	int sz=G[v].size();
	for(ll &i=iter[v];i<sz;i++){
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to]){
			ll d=dfs(e.to,t,min(e.cap,f));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}

inline ll max_flow(ll s,ll t,ll lim){
	ll flow=0;
	for(;;){
		bfs(s);
		if(level[t]<0)return flow;
		memset(iter, 0, sizeof(iter));
		ll f;
		while((f=dfs(s,t,INF))>0)flow+=f;
	}
}

ll wf[MAX_V][MAX_V];

int main(void){

	ll n,m,sum=0;
	cin >> n >> m;

	vector<pll>v(n);
	for(int i=0;i<n;i++){
		scanf("%d %d",&v[i].first,&v[i].second);
		sum+=v[i].first;
	}

	fill(wf[0],wf[MAX_V],INF);
	for(int i=0;i<MAX_V;i++)wf[i][i]=0;

	ll s=2*n,t=s+1;
	vector<pll>sp(m);
	vector<ll>p(m);
	for(int i=0;i<m;i++){
		scanf("%d %d %d",&sp[i].first,&sp[i].second,&p[i]);
		sp[i].first--,sp[i].second--;
		ll tmp=min(wf[sp[i].first][sp[i].second],p[i]);
		wf[sp[i].first][sp[i].second]=tmp;
		wf[sp[i].second][sp[i].first]=tmp;
	}

	for(int k=0;k<n;k++){
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				wf[i][j]=min(wf[i][j],wf[i][k]+wf[k][j]);
			}
		}
	}

	ll l=0,r=INF;
	while(r-l>1){

		ll mid=(l+r)/2;

		for(int i=0;i<=t;i++)G[i].clear();

		for(int i=0;i<n;i++){
			add_edge(s,i,v[i].first);
			add_edge(i+n,t,v[i].second);

			for(int j=0;j<n;j++){
				if(mid>=wf[i][j])add_edge(i,j+n,sum);
			}
		}

		if(max_flow(s,t,mid)==sum)r=mid;
		else l=mid;
	}

	if(r==INF)cout << -1 << endl;
	else cout << r << endl;

	return 0;
}

2014-03-20

0122:Summer of Phyonkichi

AOJ 探索

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0122

dfsした。

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>

using namespace std;

vector<pair<int,int> >sp;

int dx[12]={-1,0,1,2,2,2,1,0,-1,-2,-2,-2};
int dy[12]={-2,-2,-2,-1,0,1,2,2,2,1,0,-1};

int n;

bool dfs(int x,int y,int t){

	if(t>=0 && (abs(x-sp[t].first)>1 || abs(y-sp[t].second)>1))return false;
	if(t==n-1)return true;

	for(int i=0;i<12;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(nx<0 || ny<0 || 9<nx || 9<ny)continue;
		if(dfs(nx,ny,t+1))return true;
	}
	return false;
}

int main(void){

	int x,y;
	while(cin >> x >> y,x|y){
		cin >> n;
		sp.resize(n);
		for(int i=0;i<n;i++)cin >> sp[i].first >> sp[i].second;
		if(dfs(x,y,-1))cout << "OK" << endl;
		else cout << "NA" << endl;
	}

	return 0;
}

2014-03-20

0116:Rectangular Searching

AOJ データ構造

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0116

典型問題。↓を参考にした。
http://algorithms.blog55.fc2.com/blog-entry-133.html

#include<iostream>
#include<vector>
#include<stack>
#include<algorithm>

using namespace std;

typedef pair<int,int> pii;

char G[501][501];
int g[501][501];

int main(void){

	int h,w;
	while(cin >> h >> w,h|w){
		fill(g[0],g[501],0);
		for(int i=0;i<h;i++)cin >> G[i];

		for(int i=0;i<w;i++)g[0][i]=(G[0][i]=='.');
		for(int i=1;i<h;i++){
			for(int j=0;j<w;j++){
				if(G[i][j]=='.')g[i][j]=g[i-1][j]+1;
			}
		}

		int ans=0;
		for(int i=0;i<h;i++){
			stack<pii> st;
			for(int j=0;j<w;j++){
				if(st.empty() || st.top().first<g[i][j])st.push(pii(g[i][j],j));
				else if(st.top().first>g[i][j]){
					int pos;
					while(!st.empty() && st.top().first>=g[i][j]){
						pos=st.top().second;
						ans=max(ans,(j-st.top().second)*st.top().first);
						st.pop();
					}
					st.push(pii(g[i][j],pos));
				}
			}
			
			while(!st.empty()){
				ans=max(ans,(w-st.top().second)*st.top().first);
				st.pop();
			}
			
		}
		cout << ans << endl;
	}

	return 0;
}

2014-03-16

2118:Oil Company

AOJ 動的計画法

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2118

数字が書いてあるグリッドが与えられる。
この数字の中から、4近傍に隣接しているもの同士をとらないように選んだとき選んだ数字の和を最大化せよ。

前の一行を覚えておくdp。

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int dp[2][1<<20];

int main(void){

	int n;
	cin >> n;
	for(int tc=1;tc<=n;tc++){
		int h,w;
		cin >> w >> h;

		int r[20][20];
		for(int i=0;i<h;i++)
			for(int j=0;j<w;j++)cin >> r[i][j];

		fill(dp[0],dp[2],0);
		for(int i=0;i<h*w;i++){
			for (int j=0;j<(1<<w);j++)dp[(i+1)&1][j]=0;
			for(int S=0;S<(1<<w);S++){
				int x=i%w,y=i/w,nx=(S<<1)&((1<<w)-1);
				if((x==0 && (S>>(w-1)&1)) || (y==0 && (S&1)) || (x!=0 && y!=0 && ((S&1) || (S>>(w-1)&1)))){
					dp[(i+1)&1][nx]=max(dp[(i+1)&1][nx],dp[i&1][S]);
				}
				else {	
					dp[(i+1)&1][nx]=max(dp[(i+1)&1][nx],dp[i&1][S]);					
					dp[(i+1)&1][nx|1]=max(dp[(i+1)&1][nx|1],dp[i&1][S]+r[y][x]);
				}
			}
		}
		int ans=0;
		for(int i=0;i<(1<<w);i++)ans=max(ans,dp[(h*w)&1][i]);
		cout << "Case " << tc << ": " << ans << endl;
	}
	return 0;
}

2014-03-01

2488:Tree Construction

AOJ 動的計画法

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2488

区間dp。monge性を使わなくても通ってしまった。
dp[i][j]:=i~j番目までの点で木を作るときの最小コスト

#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cctype>
#include<cassert>
#include<cmath>
#include<climits>
 
#define INF (1<<29)
#define all(c) (c).begin(),(c).end()
#define D(x) cout << #x " is " << (x) << endl
#define rep(i,n) for(int i = 0; i < n; i++)
#define x first
#define y second
 
using namespace std;
 
typedef pair<int,int>pii;
typedef long long ll;
 
int dp[1001][1001];
 
int main(void){
 
  int n;
  cin >> n;
 
  vector<pii>v(n);
  rep(i,n)cin >> v[i].x >> v[i].y;
 
 
  fill(dp[0],dp[1001],INT_MAX);
  rep(i,1001)dp[i][i]=0;
 
  for(int w=0;w<n;w++){
    for(int i=0;i+w<n;i++){
      for(int s=i;s<i+w;s++){
        int cost=abs(v[i].x-v[s+1].x)+abs(v[s].y-v[i+w].y);
        dp[i][i+w]=min(dp[i][i+w],dp[i][s]+dp[s+1][i+w]+cost);
      }
    }
  }
 
  cout << dp[0][n-1] << endl;
 
  return 0;
}

↓がmonge性を使って高速化したもの。

#include<vector>
#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<string>
#include<cctype>
#include<cassert>
#include<cmath>
#include<climits>

#define INF (1<<29)
#define all(c) (c).begin(),(c).end()
#define D(x) cout << #x " is " << (x) << endl
#define rep(i,n) for(int i = 0; i < n; i++)
#define x first
#define y second

using namespace std;

typedef pair<int,int>pii;
typedef long long ll;

ll dp[1002][1002],K[1002][1002];

int main(void){

  int n;
  cin >> n;

  vector<pii>v(n);
  rep(i,n)cin >> v[i].x >> v[i].y;


  fill(dp[0],dp[1001],INT_MAX);
  fill(K[0],K[1001],-1);
  rep(i,1001)dp[i][i]=0,K[i][i]=i;

  for(int w=1;w<n;w++){
    for(int i=0;i+w<=n;i++){
      for(int s=K[i][i+w-1];s<=K[i+1][i+w];s++){
        int cost=abs(v[i].x-v[s+1].x)+abs(v[s].y-v[i+w].y);
        if(dp[i][i+w]>dp[i][s]+dp[s+1][i+w]+cost){
          dp[i][i+w]=dp[i][s]+dp[s+1][i+w]+cost;
          K[i][i+w]=s;
        }
      }
    }
  }

  cout << dp[0][n-1] << endl;

  return 0;
}