답안 #5439

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
5439 2014-05-02T10:25:54 Z gs12117 통행료 (APIO13_toll) C++
78 / 100
2500 ms 7344 KB
#include<stdio.h>
#include<algorithm>
int n,p,m;
int etob[23][2];
long long int ans;
struct edge{
	int a,b,cost;
	bool operator<(const edge&r)const{
		return cost<r.cost;
	}
};
edge eip[23];
edge eipb[300100];
int uft[100100];
long long int pnb[100100];
int cprs[100100];
long long int pn[23];
long long int npn[23];
int neb[23][2];
int nebn;
int chk[300100];
int ufs[23];
int es[23];
int elist[45][2];
int price[23];
int bchk[23];
long long int snum[23];
long long int nans;
int uftf(int x){
	if(x==uft[x])return x;
	return uft[x]=uftf(uft[x]);
}
void fillpath(int x,int y,int val){
	int i;
	bchk[x]=1;
	if(x==y)return;
	for(i=es[x];i<es[x+1];i++){
		if(bchk[elist[i][0]]==0){
			fillpath(elist[i][0],y,val);
			if(bchk[y]==1){
				if(price[elist[i][1]]>val)price[elist[i][1]]=val;
				return;
			}
		}
	}
}
void dfs(int x){
	int i;
	bchk[x]=1;
	snum[x]=npn[x];
	for(i=es[x];i<es[x+1];i++){
		if(bchk[elist[i][0]]==0){
			dfs(elist[i][0]);
			snum[x]+=snum[elist[i][0]];
			nans+=snum[elist[i][0]]*elist[i][1];
		}
	}
}
void calc(int x){
	int i,j;
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<p;i++){
		if((x>>i)%2==1){
			if(uftf(etob[i][0])==uftf(etob[i][1]))return;
			uft[uftf(etob[i][0])]=uftf(etob[i][1]);
		}
	}
	for(i=0;i<m;i++){
		chk[i]=0;
		if(uftf(eip[i].a)!=uftf(eip[i].b)){
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
			chk[i]=1;
		}
	}
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<m;i++){
		if(chk[i]==1){
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
		}
	}
	for(i=1;i<=n;i++){
		npn[i]=0;
	}
	for(i=1;i<=n;i++){
		npn[uftf(i)]+=pn[i];
		ufs[i]=uftf(i);
	}
	nebn=0;
	for(i=0;i<p;i++){
		if((x>>i)%2==1){
			neb[nebn][0]=uftf(etob[i][0]);
			neb[nebn][1]=uftf(etob[i][1]);
			price[nebn]=999999999;
			nebn++;
		}
	}
	for(i=0;i<n+3;i++){
		es[i]=0;
	}
	for(i=0;i<nebn;i++){
		es[neb[i][0]+2]++;
		es[neb[i][1]+2]++;
	}
	for(i=0;i<n+3;i++){
		es[i+1]+=es[i];
	}
	for(i=0;i<nebn;i++){
		elist[es[neb[i][0]+1]][0]=neb[i][1];
		elist[es[neb[i][0]+1]][1]=i;
		es[neb[i][0]+1]++;
		elist[es[neb[i][1]+1]][0]=neb[i][0];
		elist[es[neb[i][1]+1]][1]=i;
		es[neb[i][1]+1]++;
	}
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<m;i++){
		if(chk[i]==1){
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
		}
	}
	for(i=0;i<m;i++){
		if(uftf(eip[i].a)!=uftf(eip[i].b)){
			for(j=1;j<=n;j++){
				bchk[j]=0;
			}
			fillpath(ufs[eip[i].a],ufs[eip[i].b],eip[i].cost);
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
		}
	}
	for(i=0;i<2*nebn;i++){
		elist[i][1]=price[elist[i][1]];
	}
	for(j=1;j<=n;j++){
		bchk[j]=0;
		snum[j]=0;
	}
	nans=0;
	dfs(ufs[1]);
	if(ans<nans)ans=nans;
}
int main(){
	int i,j,tn,tm;
	scanf("%d%d%d",&n,&m,&p);
	for(i=0;i<m;i++){
		scanf("%d%d%d",&eipb[i].a,&eipb[i].b,&eipb[i].cost);
	}
	for(i=0;i<p;i++){
		scanf("%d%d",&etob[i][0],&etob[i][1]);
	}
	for(i=1;i<=n;i++){
		scanf("%lld",&pnb[i]);
	}
	std::sort(eipb,eipb+m);
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<p;i++){
		if(uftf(etob[i][0])!=uftf(etob[i][1]))uft[uftf(etob[i][0])]=uftf(etob[i][1]);
	}
	for(i=0;i<m;i++){
		chk[i]=0;
		if(uftf(eipb[i].a)!=uftf(eipb[i].b)){
			uft[uftf(eipb[i].a)]=uftf(eipb[i].b);
			chk[i]=1;
		}
	}
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<m;i++){
		if(chk[i]==1){
			uft[uftf(eipb[i].a)]=uftf(eipb[i].b);
		}
	}
	tn=0;
	for(i=1;i<=n;i++){
		if(cprs[uftf(i)]==0){
			tn++;
			cprs[uftf(i)]=tn;
		}
	}
	for(i=1;i<=n;i++){
		pn[cprs[uftf(i)]]+=pnb[i];
	}
	for(i=0;i<p;i++){
		etob[i][0]=cprs[uftf(etob[i][0])];
		etob[i][1]=cprs[uftf(etob[i][1])];
	}
	for(i=0;i<m;i++){
		eipb[i].a=cprs[uftf(eipb[i].a)];
		eipb[i].b=cprs[uftf(eipb[i].b)];
	}
	tm=0;
	for(i=1;i<=tn;i++){
		uft[i]=i;
	}
	for(i=0;i<m;i++){
		if(uftf(eipb[i].a)!=uftf(eipb[i].b)){
			eip[tm]=eipb[i];
			tm++;
			uft[uftf(eipb[i].a)]=uftf(eipb[i].b);
		}
	}
	n=tn;
	m=tm;
	for(i=1;i<(1<<p);i++){
		calc(i);
	}
	printf("%lld",ans);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7344 KB Output is correct
2 Correct 0 ms 7344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7344 KB Output is correct
2 Correct 0 ms 7344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7344 KB Output is correct
2 Correct 0 ms 7344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 264 ms 7344 KB Output is correct
2 Correct 276 ms 7344 KB Output is correct
3 Correct 272 ms 7344 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2500 ms 7340 KB Program timed out
2 Halted 0 ms 0 KB -