| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 4560 |
2013-10-31T16:59:31 Z |
cki86201 |
Toll (APIO13_toll) |
C++ |
|
92 ms |
1516 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
#define Ma(x) (int *)malloc(x*sizeof(int))
#define Ca(x) (int *)calloc(x,sizeof(int))
typedef long long ll;
typedef pair<int,int> Pi;
// O(2^K * (M+N)log N), 34~56point dirty code;
const int MV = 1010;
const int ME = 10010;
int N,M,K;
ll ans;
int ord[ME],ord2[MV];
Pi add[22];
struct UF{
int p[MV],mem[MV];
void init(){for(int i=1;i<=N;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];
void init(){for(int i=0;i<MV;i++)st[i]=0;}
void addedge(int s,int d,int l,int c){next[c]=st[s],st[s]=c,en[c]=d,len[c]=l;}
void add(int s,int d,int l,int c){addedge(s,d,l,c<<1),addedge(d,s,l,c<<1|1);}
}I,MS,A;
bool comp1(const int &a,const int &b){return I.len[a<<1]<I.len[b<<1];}
bool comp2(const int &a,const int &b){return MS.len[a<<1]<MS.len[b<<1];}
bool check[MV],as[MV<<1];
int wei[MV],inp[MV];
void bfs(int s,int d,int l)
{
int Q[MV],pre[MV],num[MV];
memset(check,0,sizeof(check));
int *fr=Q,*re=Q;
*fr++=s,pre[s]=-1,check[s]=1;
while(fr!=re){
int t=*re++;
for(int i=A.st[t];i;i=A.next[i]){
if(check[A.en[i]])continue;
int tt = A.en[i];
*fr++=tt;
check[tt]=1;
pre[tt]=t;
num[tt]=i;
if(tt==d){
int tmp=tt;
while(tmp!=s){
if(A.len[num[tmp]]<0){
int k=num[tmp];
A.len[k]=A.len[k^1]=l;
}
tmp=pre[tmp];
}
fr=re;
break;
}
}
}
}
ll dfs(int x)
{
check[x]=1;
ll ret=0;
for(int i=A.st[x];i;i=A.next[i]){
if(check[A.en[i]])continue;
int d=A.en[i];
check[d]=1;
ret+=dfs(d);
wei[x]+=wei[d];
if(as[i])ret+=(ll)A.len[i]*wei[d];
}
wei[x]+=inp[x];
return ret;
}
ll MST(int x)
{
memset(as,0,sizeof(as));
A.init();
uf.init();
int i,cnt=0;
for(i=0;i<K;i++){
if(x&(1<<i)){
int x=add[i].X,y=add[i].Y;
if(!uf.Union(x,y))return -1;
A.add(x,y,-1,++cnt);
as[cnt<<1]=as[cnt<<1|1]=1;
}
}
for(i=1;i<N;i++){
int t=ord2[i];
int x=MS.en[t<<1],y=MS.en[t<<1|1];
if(uf.Union(x,y)){A.add(x,y,MS.len[t<<1],++cnt);continue;}
bfs(x,y,MS.len[t<<1]);
}
memset(check,0,sizeof(check));
memset(wei,0,sizeof(wei));
return dfs(1);
}
void MST_cut()
{
int i,cnt=0;
uf.init();
for(i=1;i<=M;i++){
int t=ord[i];
int x=I.en[t<<1];
int y=I.en[t<<1|1];
if(uf.Union(x,y))MS.add(x,y,I.len[t<<1],++cnt);
}
for(i=1;i<N;i++)ord2[i]=i;
sort(ord2+1,ord2+N,comp2);
}
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);
I.add(x,y,z,i);
}
for(i=1;i<=M;i++)ord[i]=i;
sort(ord+1,ord+1+M,comp1);
MST_cut();
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);
for(i=0;i<(1<<K);i++){
ans=max(ans,MST(i));
}
printf("%lld\n",ans);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
0 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
1516 KB |
Output is correct |
| 2 |
Correct |
32 ms |
1516 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
1512 KB |
SIGSEGV Segmentation fault |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Halted |
0 ms |
0 KB |
- |
