| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4562 |
2013-10-31T19:41:21 Z |
cki86201 |
Toll (APIO13_toll) |
C++ |
|
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=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=0;i<K;i++)add[i].X=gro[add[i].X],add[i].Y=gro[add[i].Y];
}
ll wei[22];
int T;
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(i<=T)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);
}
}
T=NE.c;
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()
{
// freopen("toll.in5.1","r",stdin);
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\n",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
36544 KB |
Output is correct |
| 2 |
Correct |
0 ms |
36544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
36544 KB |
Output is correct |
| 2 |
Correct |
0 ms |
36544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
36544 KB |
Output is correct |
| 2 |
Correct |
4 ms |
36544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
212 ms |
36544 KB |
Output is correct |
| 2 |
Correct |
224 ms |
36544 KB |
Output is correct |
| 3 |
Correct |
196 ms |
36544 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1328 ms |
36544 KB |
Output is correct |
| 2 |
Execution timed out |
2500 ms |
36544 KB |
Program timed out |
| 3 |
Halted |
0 ms |
0 KB |
- |
