Submission #5433

#	Time	Username	Problem	Language	Result	Execution time	Memory
5433		gs12117	Toll (APIO13_toll)	C++98	0 / 100	0 ms	9300 KiB

toll

#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[300100];
int uft[100100];
long long int pn[100100];
long long int npn[100100];
int neb[23][2];
int nebn;
int chk[300100];
int ufs[100100];
int es[100100];
int elist[45][2];
int price[23];
int bchk[100100];
int snum[100100];
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[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][0]+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);
		}
		else 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;
	scanf("%d%d%d",&n,&m,&p);
	for(i=0;i<m;i++){
		scanf("%d%d%d",&eip[i].a,&eip[i].b,&eip[i].cost);
	}
	for(i=0;i<p;i++){
		scanf("%d%d",&etob[i][0],&etob[i][1]);
	}
	for(i=1;i<=n;i++){
		scanf("%d",&pn[i]);
	}
	std::sort(eip,eip+m);
	for(i=1;i<(1<<p);i++){
		calc(i);
	}
	printf("%d",ans);
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22