oj.uz

답안 #4561

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4561 2013-10-31T19:25:38 Z cki86201 통행료 (APIO13_toll) C++
78 / 100
 2500 ms 36544 KB 
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<vector>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<ctype.h>
using namespace std;

#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> Pi;

// O( 2^K*K^2 + MlogN ), maybe 78 point dirty code;
const int MV = 100010;
const int ME = 600060;

int N,M,K;
struct UF{
	int p[MV],mem[MV];
	void init(int x){for(int i=1;i<=x;i++)p[i]=i,mem[i]=1;}
	int Find(int x){
		int t=x;
		while(p[t]!=t)t=p[t];
		while(x!=t)p[x]=t,x=p[x];
		return x;
	}
	bool Union(int x,int y){
		x=Find(x),y=Find(y);
		if(x==y)return false;
		if(mem[x]>mem[y])p[y]=x,mem[x]+=mem[y];
		else p[x]=y,mem[y]+=mem[x];
		return true;
	}
}uf;

struct Graph{
	int st[MV], en[ME], len[ME], next[ME];
	int c;
	Graph(){c=1;}
	void init(int x){for(int i=1;i<=x;i++)st[i]=0;c=1;}
	void addedge(int s,int d,int l){++c,next[c]=st[s],st[s]=c,en[c]=d,len[c]=l;}
	void add(int s,int d,int l){addedge(s,d,l),addedge(d,s,l);}
}I,MST,GR,NE;

int inp[MV];
int gro[MV];
ll wi[23];
int Ka;
int sor[1000010];
ll ans;
Pi add[23];
bool cut[MV<<1];
bool check[MV];

void make_mst()
{
	uf.init(N);
	int i;
	for(i=1;i<=1000000;i++){
		if(sor[i]){
			int x=I.en[sor[i]<<1],y=I.en[sor[i]<<1|1];
			if(uf.Union(x,y)){
				MST.add(x,y,I.len[sor[i]<<1]);
			}
		}
	}
//	for(i=2;i<2*N;i++)printf("%d ",MST.en[i]);
}

void dfs(int x,int c)
{
	gro[x]=c;
	wi[c]+=inp[x];
	check[x]=1;
	for(int i=MST.st[x];i;i=MST.next[i]){
		if(!check[MST.en[i]]&&!cut[i])dfs(MST.en[i],c);
	}
}

void make_mst2()
{
	uf.init(N);
	int i;
	for(i=0;i<K;i++)uf.Union(add[i].X,add[i].Y);
	for(i=1;i<N;i++){
		if(!uf.Union(MST.en[i<<1],MST.en[i<<1|1]))cut[i<<1]=cut[i<<1|1]=1;
	}
//	for(i=2;i<2*N;i++)printf("%d ",cut[i]);
	for(i=1;i<=N;i++)if(!check[i])dfs(i,++Ka);
	for(i=1;i<N;i++){if(cut[i<<1])GR.add(gro[MST.en[i<<1]],gro[MST.en[i<<1|1]],MST.len[i<<1]);}
//	for(i=1;i<=N;i++)printf("%d ",gro[i]);
//	puts("");
//	for(i=2;i<2*cnt;i++)printf("%d ",GR.en[i]);
	for(i=0;i<K;i++)add[i].X=gro[add[i].X],add[i].Y=gro[add[i].Y];
}

ll wei[22];
bool T[44];
bool chk[22];

void bfs(int s,int d,int l)
{
	int Q[22],pre[22],fr=1,re=0,i;
	memset(chk,0,sizeof(chk));
	Q[0]=s;
	chk[s]=1;
	while(fr!=re){
		for(i=NE.st[Q[re++]];i;i=NE.next[i]){
			int t=NE.en[i];
			if(chk[t])continue;
			Q[fr++]=t;
			chk[t]=1;
			pre[t]=i;
			if(t==d){
				int tmp=t;
				while(tmp!=s){
					int u=pre[tmp];
					if(NE.len[u]<0)NE.len[u]=NE.len[u^1]=l;
					tmp=NE.en[u^1];
				}
				return;
			}
		}
	}
}

ll dfs(int x)
{
	chk[x]=1;
	ll ret=0;
	for(int i=NE.st[x];i;i=NE.next[i]){
		if(chk[NE.en[i]])continue;
		int d=NE.en[i];
		ret+=dfs(d);
		wei[x]+=wei[d];
		if(T[i])ret+=wei[d]*NE.len[i];
	}
	wei[x]+=wi[x];
	return ret;
}

ll solve(int x)
{
	uf.init(K+1);
	NE.init(K+1);
	int i;
	for(i=0;i<K;i++){
		if(x&(1<<i)){
			if(!uf.Union(add[i].X,add[i].Y))return -1;
			NE.add(add[i].X,add[i].Y,-1);
		}
	}
	for(i=2;i<=NE.c;i++)T[i]=1;
	for(i=NE.c+1;i<2*Ka;i++)T[i]=0;
	for(i=1;i<Ka;i++){
		int x=GR.en[i<<1], y=GR.en[i<<1|1];
		if(uf.Union(x,y))NE.add(x,y,GR.len[i<<1]);
		else bfs(x,y,GR.len[i<<1]);
	}
	memset(chk,0,sizeof(chk));
	memset(wei,0,sizeof(wei));
	return dfs(1);
}

int getInt()
{
	int a=0;
	char c=getchar();
	while(isdigit(c)){
		a=(a<<3)+(a<<1)+c-'0';
		c=getchar();
	}
	return a;
}

int main()
{
	scanf("%d%d%d",&N,&M,&K);
	int i;
	for(i=1;i<=M;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		sor[z]=i;
		I.add(x,y,z);
	}
	for(i=0;i<K;i++)scanf("%d%d",&add[i].X,&add[i].Y);
	for(i=1;i<=N;i++)scanf("%d",inp+i);
	make_mst();
	make_mst2();
	for(i=0;i<(1<<K);i++){
		ans=max(ans,solve(i));
	}
	printf("%lld",ans);
	return 0;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 36544 KB Output is correct
2 Correct 0 ms 36544 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 36544 KB Output is correct
2 Correct 0 ms 36544 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 36544 KB Output is correct
2 Correct 4 ms 36544 KB Output is correct

Subtask #4
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 216 ms 36544 KB Output is correct
2 Correct 220 ms 36544 KB Output is correct
3 Correct 216 ms 36544 KB Output is correct

Subtask #5
0.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1312 ms 36544 KB Output is correct
2 Execution timed out 2500 ms 36544 KB Program timed out
3 Halted 0 ms 0 KB -