QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#518592#1825. The King's GuardsmaxyzfjWA 17ms17772kbC++143.6kb2024-08-13 22:30:192024-08-13 22:30:19

Judging History

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

  • [2024-08-13 22:30:19]
  • 评测
  • 测评结果:WA
  • 用时:17ms
  • 内存:17772kb
  • [2024-08-13 22:30:19]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define mp(x,y) make_pair(x,y)
#define lb(x) (x&(-x))
#define fi first
#define se second
#define pii pair<int,int>
int read(){
	int x=0,f=1;
    char ch=getchar();
	while(ch<'0'||ch>'9'){
    	if(ch=='-')f=-1;
		ch=getchar();
    }
	while(ch>='0'&&ch<='9'){
    	x=x*10+ch-48;
		ch=getchar();
    }
	return x*f;
}
void writ(int x){
    if(x<0){
		putchar('-'),x=-x;
	}
    if(x>9){
		writ(x/10);
	}
    putchar(x%10 +'0');
}
void write(int x,char p=' '){
    writ(x);
    putchar(p);
}
string sread(){
    string t="";
    char c=getchar();
    while(c==' '||c=='\t'||c=='\r'||c=='\n'||c==0||c==EOF){
        c=getchar();
    }
    while(!(c==' '||c=='\t'||c=='\r'||c=='\n'||c==0||c==EOF)){
        t+=c,c=getchar();
    }
    return t;
}
const int QMR=1000000007,LSJ=998244353,inf=2e18,N=305,M=5e4+5,K=2e5+5;
//int cal(int a,int b=QMR-2){
//	int base=a,ret=1;
//	while(b){
//		if(b&1){
//			ret=ret*base%QMR;
//		}
//		base=base*base%QMR;
//		b>>=1;
//	}
//	return ret;
//}
mt19937 rnd(time(0)^clock());
namespace qwq{
	int head[K],tot=1,s,t,ans,anscost,d[K],cur[K],v[K];
	struct edges{
		int to,nxt,flow,cost;
	}edge[K*2];
	void add(int from,int to,int f,int c){
		++tot;
		edge[tot].to=to;
		edge[tot].flow=f;
		edge[tot].nxt=head[from];
		edge[tot].cost=c;
		head[from]=tot;
		++tot;
		edge[tot].to=from;
		edge[tot].flow=0;
		edge[tot].nxt=head[to];
		edge[tot].cost=-c;
		head[to]=tot;
	}
	bool spfa(int st){
		memset(v,0,sizeof(v));
		queue<int>q;
		for(int i=0;i<=t;i++){
			d[i]=inf;
		}
		d[st]=0;
		v[st]=1;
		q.push(st);
		int flag=0;
		while(q.size()){
			int x=q.front();
			q.pop();
			v[x]=0;
			for(int i=head[x];i;i=edge[i].nxt){
				int y=edge[i].to,z=edge[i].cost,zyh=edge[i].flow;
				if(d[y]>d[x]+z&&zyh){
					d[y]=d[x]+z;
					if(y==t){
						flag=1;
					}
					if(!v[y]){
						q.push(y);
						v[y]=1;
					}
				}
			}
		}
		return flag;
	}
	int dfs(int x,int flow){
		if(x==t){
			return flow;
		}
		v[x]=1;
		int rst=flow;
		for(int i=cur[x];i&&rst;i=edge[i].nxt){
			cur[x]=i;
			int y=edge[i].to,z=edge[i].flow,w=edge[i].cost;
			if(v[y]==0&&z>0&&d[y]==d[x]+w){
				int k=dfs(y,min(rst,z));
				rst-=k;
				edge[i].flow-=k;
				edge[i^1].flow+=k;
				anscost+=w*k;
			}
		}
		v[x]=0;
		return flow-rst;
	}
	void dinic(){
		while(spfa(s)){
			memcpy(cur,head,sizeof(head));
			ans+=dfs(s,inf);
		}
	}
}
int fa[N<<1];
struct node{
	int x,y,z;
}a[M];
bool cmp(node aa,node b){
	return aa.z<b.z;
}
int get(int x){
	if(x==fa[x])return x;
	return fa[x]=get(fa[x]);
}
basic_string<pii >g[N];
int n,m,k;
using qwq::add;
signed main(){
    //freopen("qmr.in","r",stdin);
    //freopen("qmr.out","w",stdout);
    n=read();m=read();k=read();qwq::s=2*n+k+1;qwq::t=qwq::s+1;
	for(int i=1;i<n*2;i++){
		fa[i]=i;
	} 
	for(int i=1;i<=m;i++){
		a[i].x=read();
		a[i].y=read();
		a[i].z=read();
	}
	for(int i=1;i<=k;i++){
		add(qwq::s,i,1,0);
	}
	for(int i=1;i<=k;i++){
		int qmr=read();
		while(qmr--){
			int x=read();
			add(i,x+k,1,0);
		}
	}
	sort(a+1,a+m+1,cmp);
	int cnt=0,sum=0;
	for(int i=1;i<=m;i++){
		int x=get(a[i].x),y=get(a[i].y);
		if(x!=y){
			++cnt;
			sum+=a[i].z;
			fa[x]=n+cnt;
			fa[y]=n+cnt;
			add(x+k,cnt+n+k,1,0);
			add(y+k,cnt+n+k,1,0);
			add(cnt+n+k,qwq::t,1,-a[i].z);
		}
	}
	int t=inf/31415926,tt=0;
	for(int i=1;i<2*n;i++){
		if(fa[i]==i){
			add(i+k,qwq::t,1,-t);tt+=t;
		}
	} 
	qwq::dinic();
	qwq::anscost+=tt;
	if(qwq::anscost>0){
		puts("-1");
	}
	else write(sum+qwq::anscost);
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 11888kb

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: 0
Accepted
time: 3ms
memory: 11956kb

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:

429 

result:

ok answer is '429'

Test #3:

score: 0
Accepted
time: 2ms
memory: 9800kb

input:

10 43 3
1 3 656
2 6 856
4 10 99
5 6 900
2 7 766
4 7 582
2 8 135
5 7 831
3 5 12
3 10 789
1 8 66
4 9 390
1 7 238
6 7 960
1 4 624
3 9 602
7 10 366
5 8 526
2 9 561
6 10 722
2 5 904
3 4 35
1 9 768
5 9 457
6 8 61
4 6 192
4 5 96
5 10 747
8 9 611
7 8 953
3 8 449
2 4 228
1 6 197
9 10 160
3 6 869
1 2 785
4 8 ...

output:

526 

result:

ok answer is '526'

Test #4:

score: 0
Accepted
time: 3ms
memory: 10168kb

input:

277 9038 1
226 260 740
44 226 376
151 263 611
67 269 241
120 181 677
259 271 782
37 52 310
48 152 452
168 266 823
85 234 100
46 201 738
129 153 301
69 147 434
13 72 764
13 234 316
171 222 398
214 255 21
112 158 430
20 118 407
45 152 971
205 214 272
221 275 362
198 268 472
117 176 207
31 75 652
139 1...

output:

5375 

result:

ok answer is '5375'

Test #5:

score: 0
Accepted
time: 10ms
memory: 10752kb

input:

297 27966 132
15 197 980
226 259 950
161 168 142
118 176 834
157 221 806
24 210 432
212 242 838
110 166 177
78 170 801
52 166 3
89 213 448
45 170 626
250 251 268
93 222 679
7 128 839
5 7 320
132 191 1
192 295 717
36 231 542
162 175 508
173 178 458
211 272 926
46 168 145
19 150 805
165 262 198
50 179...

output:

775 

result:

ok answer is '775'

Test #6:

score: 0
Accepted
time: 2ms
memory: 11892kb

input:

7 7 4
1 3 7
1 4 6
2 3 5
2 4 6
4 5 10
4 6 10
4 7 10
5 4 3 2 7 5
6 5 2 6 7 4 1
2 2 3
6 7 2 5 3 1 6

output:

17 

result:

ok answer is '17'

Test #7:

score: 0
Accepted
time: 7ms
memory: 15640kb

input:

300 44850 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

1000 

result:

ok answer is '1000'

Test #8:

score: 0
Accepted
time: 17ms
memory: 17772kb

input:

300 44850 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

1000 

result:

ok answer is '1000'

Test #9:

score: 0
Accepted
time: 13ms
memory: 13032kb

input:

300 44850 150
1 2 4
1 3 4
1 4 4
1 5 3
1 6 10
1 7 4
1 8 8
1 9 5
1 10 4
1 11 9
1 12 9
1 13 1
1 14 3
1 15 5
1 16 7
1 17 5
1 18 2
1 19 6
1 20 4
1 21 10
1 22 5
1 23 7
1 24 2
1 25 2
1 26 4
1 27 4
1 28 5
1 29 8
1 30 10
1 31 9
1 32 1
1 33 7
1 34 5
1 35 4
1 36 6
1 37 8
1 38 1
1 39 2
1 40 1
1 41 1
1 42 1
1 43...

output:

249 

result:

ok answer is '249'

Test #10:

score: 0
Accepted
time: 8ms
memory: 13788kb

input:

300 44850 150
1 2 70
1 3 26
1 4 76
1 5 74
1 6 98
1 7 72
1 8 66
1 9 25
1 10 36
1 11 57
1 12 8
1 13 88
1 14 98
1 15 33
1 16 85
1 17 56
1 18 16
1 19 62
1 20 41
1 21 81
1 22 18
1 23 15
1 24 69
1 25 11
1 26 29
1 27 62
1 28 64
1 29 41
1 30 92
1 31 29
1 32 99
1 33 40
1 34 30
1 35 23
1 36 49
1 37 6
1 38 84
...

output:

1299 

result:

ok answer is '1299'

Test #11:

score: 0
Accepted
time: 8ms
memory: 15132kb

input:

300 44850 150
1 2 3
1 3 2
1 4 20
1 5 77
1 6 77
1 7 23
1 8 39
1 9 57
1 10 83
1 11 60
1 12 6
1 13 78
1 14 64
1 15 62
1 16 41
1 17 88
1 18 77
1 19 58
1 20 39
1 21 18
1 22 43
1 23 26
1 24 40
1 25 61
1 26 23
1 27 6
1 28 47
1 29 100
1 30 59
1 31 92
1 32 60
1 33 13
1 34 57
1 35 55
1 36 99
1 37 77
1 38 63
1...

output:

1310 

result:

ok answer is '1310'

Test #12:

score: 0
Accepted
time: 6ms
memory: 12732kb

input:

300 44551 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

-1

result:

ok answer is '-1'

Test #13:

score: 0
Accepted
time: 3ms
memory: 11388kb

input:

300 44552 299
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

2 

result:

ok answer is '2'

Test #14:

score: -100
Wrong Answer
time: 7ms
memory: 12968kb

input:

300 44552 300
1 2 1
1 3 1
1 4 1
1 5 1
1 6 1
1 7 1
1 8 1
1 9 1
1 10 1
1 11 1
1 12 1
1 13 1
1 14 1
1 15 1
1 16 1
1 17 1
1 18 1
1 19 1
1 20 1
1 21 1
1 22 1
1 23 1
1 24 1
1 25 1
1 26 1
1 27 1
1 28 1
1 29 1
1 30 1
1 31 1
1 32 1
1 33 1
1 34 1
1 35 1
1 36 1
1 37 1
1 38 1
1 39 1
1 40 1
1 41 1
1 42 1
1 43 1
...

output:

2 

result:

wrong answer expected '-1', found '2'