QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#31554 | #1825. The King's Guards | RobeZH# | WA | 3ms | 3864kb | C++ | 2.8kb | 2022-05-09 05:44:17 | 2022-05-09 05:44:18 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
typedef vector<int> vi;
const int N=305;
struct edge{
int a,b,c;
}e[N];
int f[N];
int fa(int x){return f[x]==x?x:f[x]=fa(f[x]);}
int n,r,k,top,S,T;
set<int>g[N*3];
bool in[N*3];
void add(int x,int y,int z){
g[x].insert(y);
}
int col[N];
bool dfsg(int x){
if(x==T)return 1;
in[x]=1;
for(int v:g[x])if(!in[v]&&dfsg(v)){
//printf("success:%d %d\n",x,v);
g[v].insert(x);
g[x].erase(v);
return 1;
}
return 0;
}
bool flow(){
rep(i,top)in[i]=0;
return dfsg(S);
}
set<int>t[N];
vi res;
void dfst(int x,int fa){
res.pb(x);
for(int v:t[x])if(v!=fa)dfst(v,x);
}
int main(){
scanf("%d%d%d",&n,&r,&k);
rep(i,n)f[i]=i;
rep(i,r)scanf("%d%d%d",&e[i].a,&e[i].b,&e[i].c);
sort(e+1,e+r+1,[](edge u,edge v){return u.c<v.c;});
top=0;
int ans=0;
rep(i,r){
int u=fa(e[i].a),v=fa(e[i].b);
if(u!=v){
f[u]=v;
e[++top]=e[i];
ans+=e[i].c;
t[e[i].a].insert(e[i].b);
t[e[i].b].insert(e[i].a);
}
}
//printf("%d\n",ans);
r=top;
//k n 2 top
S=k+n+1,T=S+1,top=T;
rep(i,k)add(S,i,1);
rep(i,k){
int num;scanf("%d",&num);
rep(j,num){
int x;scanf("%d",&x);
add(i,k+x,1);
}
}
rep(i,n)if(!col[i]){
res.clear();
dfst(i,0);
++top;
for(int x:res)col[x]=top,add(x,top,1);
add(top,T,1);
}
rep(i,n-r)if(!flow()){
puts("-1");
return 0;
}
int flw=n-r;
for(int i=r;i;--i){
int to=0;
for(int x:g[col[e[i].a]])if(k<x&&x<=k+n)to=x;
to-=k;
//printf("%d\n",to);
t[e[i].a].erase(e[i].b);
t[e[i].b].erase(e[i].a);
res.clear();dfst(e[i].a,0);
bool flag=0;
for(int x:res)if(x==to){
flag=1;break;
}
if(flag){
res.clear();dfst(e[i].b,0);
}
++top;
for(int x:res)g[k+x].erase(col[x]),g[k+x].insert(top),col[x]=top;
g[top].insert(T);
if(flow()){
++flw;ans-=e[i].c;
//printf("%d %d %d\n",e[i].a,e[i].b,e[i].c);
}else{
for(int x:res)col[x]=col[to],g[k+x].erase(top),g[k+x].insert(col[x]);
--top;
t[e[i].a].insert(e[i].b);
t[e[i].b].insert(e[i].a);
}
}
if(flw!=k){
puts("-1");
return 0;
}
printf("%d\n",ans);
}
/*
5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3864kb
input:
5 6 2 1 2 1 1 3 4 2 4 2 2 5 5 3 4 7 4 5 3 2 1 2 2 2 4
output:
8
result:
ok answer is '8'
Test #2:
score: -100
Wrong Answer
time: 3ms
memory: 3848kb
input:
10 19 6 1 5 761 6 8 606 3 9 648 2 4 115 5 8 814 1 2 712 4 10 13 5 10 797 3 4 956 1 7 73 5 7 192 2 7 110 5 9 302 3 6 120 6 9 494 1 3 668 3 7 966 6 10 974 3 8 41 2 10 5 3 6 4 3 2 1 7 2 10 8 3 10 7 8 2 2 1
output:
237
result:
wrong answer expected '429', found '237'