tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

PKU 3422, 2762

久しぶりにPOJ Monthlyでもやってみようと思ってやることにしました。

3422: Kaka's Matrix Travels
いつしかこのブログに書いたはずのDiv1Hardとほとんど同じ問題です。まったく同じ最小費用流をすれば解けます。

#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstdio>
using namespace std;

typedef int Weight;
const Weight INF=99999999;

struct Edge{
	int dst,cap;Weight cost,rev;
};
typedef vector<Edge> Node;
typedef vector<Node> Graph;

//srcからdstへ向かう容量cap,コストcostの辺をグラフに追加する
void add_edge(Graph &G,int src,int dst,Weight cap,Weight cost){
	G[src].push_back((Edge){dst,cap,cost,G[dst].size()});
	G[dst].push_back((Edge){src,0,-cost,G[src].size()-1});
}

//sからtへの流量fの最小費用流を求める
//流せない場合は-1を返す
int min_cost_flow(Graph &G,int s,int t,int f){
	typedef pair<int,int> P;
	int res=0;
	int V=G.size();
	vector<Weight> h(V,0);
	vector<int> prevv(V);
	vector<int> preve(V);
	
	while(f>0){
		priority_queue<P,vector<P>,greater<P> > que;
		vector<Weight> dist(V,INF);
		dist[s]=0;
		que.push(P(0,s));
		while(!que.empty()){
			P p=que.top();que.pop();
			int v=p.second;
			if(dist[v]<p.first)continue;
			for(int i=0;i<(int)G[v].size();i++){
				Edge &e=G[v][i];
				if(e.cap>0&&dist[e.dst]>dist[v]+e.cost+h[v]-h[e.dst]){
					dist[e.dst]=dist[v]+e.cost+h[v]-h[e.dst];
					prevv[e.dst]=v;
					preve[e.dst]=i;
					que.push(P(dist[e.dst],e.dst));
				}
			}
		}
		if(dist[t]==INF){	
			return -1;
		}
		for(int v=0;v<V;v++)h[v]+=dist[v];

		int d=f;
		for(int v=t;v!=s;v=prevv[v]){
			d=min(d,G[prevv[v]][preve[v]].cap);
		}
		f-=d;
		res+=d*h[t];
		for(int v=t;v!=s;v=prevv[v]){
			Edge &e=G[prevv[v]][preve[v]];
			e.cap-=d;
			G[v][e.rev].cap+=d;
		}
	}
	return res;
}
int c[100][100];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	Graph g=Graph(2*a*a+2);
	int S=2*a*a;
	int T=2*a*a+1;
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			scanf("%d",&c[i][j]);
			add_edge(g,i*a+j,i*a+j+a*a,1,1000-c[i][j]);
			add_edge(g,i*a+j,i*a+j+a*a,9999,1000);
		}
	}
	add_edge(g,S,0,99999,0);
	add_edge(g,2*a*a-1,T,99999,0);
	for(int i=0;i<a;i++){
		for(int j=0;j<a;j++){
			if(i<a-1)add_edge(g,i*a+j+a*a,(i+1)*a+j,9999,0);
			if(j<a-1)add_edge(g,i*a+j+a*a,i*a+j+1,9999,0);
		}
	}
	printf("%d\n",1000*(2*a-1)*b-min_cost_flow(g,S,T,b));
}

2762: Going from u to v or from v to u?
高2のPKUガチ勢していたときは解けなかった問題。n<1000,m<6000なのにO(n+m)でも結構時間を使います(vector使ったら1秒以上かかりそう)
強連結成分分解をして、できたグラフが直線グラフになっていればYesです。

#include<stdio.h>
#include<algorithm>
using namespace std;
int next[10000];
int first[2000];
int to[10000];
int next2[10000];
int first2[2000];
int to2[10000];
int num[2000];
int rev[2000];
int sccnum[2000];
int in[2000];
int out[2000];
int now;
void dfs1(int a){
	num[a]=now;
	for(int i=first[a];~i;i=next[i]){
		if(!~num[to[i]])dfs1(to[i]);
	}
	rev[now++]=a;
}
void dfs2(int a){
	sccnum[a]=now;
	for(int i=first2[a];~i;i=next2[i]){
		if(!~sccnum[to2[i]])dfs2(to2[i]);
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int a,b;
		scanf("%d%d",&a,&b);
		for(int i=0;i<a;i++)first[i]=first2[i]=num[i]=rev[i]=sccnum[i]=-1;
		for(int i=0;i<a;i++)in[i]=out[i]=-1;
		for(int i=0;i<b;i++)next[i]=next2[i]=-1;
		for(int i=0;i<b;i++){
			int c,d;
			scanf("%d%d",&c,&d);
			c--;d--;
			next[i]=first[c];
			first[c]=i;
			to[i]=d;
			next2[i]=first2[d];
			first2[d]=i;
			to2[i]=c;
		}
		now=0;
		for(int i=0;i<a;i++){
			if(!~num[i])dfs1(i);
		}
		now=0;
		for(int i=a-1;i>=0;i--){
			if(!~sccnum[rev[i]]){
				dfs2(rev[i]);
				now++;
			}
		}
	//	for(int i=0;i<a;i++)printf("%d\n",sccnum[i]);
		bool ok=true;
		for(int i=0;i<a;i++){
			for(int j=first[i];~j;j=next[j]){
				if(sccnum[i]==sccnum[to[j]])continue;
				if(~in[sccnum[to[j]]]&&in[sccnum[to[j]]]!=sccnum[i])ok=false;
				if(!~in[sccnum[to[j]]])in[sccnum[to[j]]]=sccnum[i];
				if(~out[sccnum[i]]&&out[sccnum[i]]!=sccnum[to[j]])ok=false;
				if(!~out[sccnum[i]])out[sccnum[i]]=sccnum[to[j]];
			}
		}
		int noin=0;
		int noout=0;
		for(int i=0;i<now;i++){
			if(!~in[i])noin++;
			if(!~out[i])noout++;
		}
		if(noin>1||noout>1)ok=false;
		if(ok)printf("Yes\n");
		else printf("No\n");
	}
}

追記:ソース間違えたのではりなおしました。