QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31554#1825. The King's GuardsRobeZH#WA 3ms3864kbC++2.8kb2022-05-09 05:44:172022-05-09 05:44:18

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-09 05:44:18]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3864kb
  • [2022-05-09 05:44:17]
  • 提交

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'