QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#20101#1825. The King's Guardsconqueror_of_zky#WA 9ms16680kbC++202.3kb2022-02-14 19:12:382022-05-03 09:04:14

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-03 09:04:14]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:16680kb
  • [2022-02-14 19:12:38]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int maxn=500010;

bool vis[maxn];
int n,m,s=100001,t=100002,x,y,z,f,dis[maxn],pre[maxn],last[maxn],flow[maxn],maxflow,mincost;
//dis最小花费;pre每个点的前驱;last每个点的所连的前一条边;flow源点到此处的流量 
struct Edge{
	int to,next,flow,dis;//flow流量 dis花费 
}edge[maxn];
int head[maxn],num_edge; 
queue <int> q;
void add_edge(int from,int to,int flow,int dis)
{
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	edge[num_edge].flow=flow;
	edge[num_edge].dis=dis;
	head[from]=num_edge;
}
inline void add(int u,int v,int w,int c)
{
	add_edge(u,v,w,c),add_edge(v,u,0,-c);
}
bool spfa(int s,int t)
{
	memset(dis,0x7f,sizeof(dis));
	memset(flow,0x7f,sizeof(flow));
	memset(vis,0,sizeof(vis));
	q.push(s); vis[s]=1; dis[s]=0; pre[t]=-1;
	
	while (!q.empty())
	{
		int now=q.front();
		q.pop();
		vis[now]=0;
		for (int i=head[now]; i!=-1; i=edge[i].next)
		{
			if (edge[i].flow>0 && dis[edge[i].to]>dis[now]+edge[i].dis)//正边 
			{
				dis[edge[i].to]=dis[now]+edge[i].dis;
				pre[edge[i].to]=now;
				last[edge[i].to]=i;
				flow[edge[i].to]=min(flow[now],edge[i].flow);//
				if (!vis[edge[i].to])
				{
					vis[edge[i].to]=1;
					q.push(edge[i].to);
				}
			}
		}
	}
	return pre[t]!=-1;
}

void MCMF()
{
	while (spfa(s,t))
	{
		int now=t;
		maxflow+=flow[t];
		mincost+=flow[t]*dis[t];
		while (now!=s)
		{//从源点一直回溯到汇点 
			edge[last[now]].flow-=flow[t];//flow和dis容易搞混 
			edge[last[now]^1].flow+=flow[t];
			now=pre[now];
		}
	}
}
int U[100005],V[100005],W[100005];
int main()
{
	memset(head,-1,sizeof(head)); num_edge=-1;
	int n,r,g;
	cin >> n >> r >> g;
	for(int i=1;i<=n;i++)
		add(s,i,1,0);
	int now=n;
	for(int i=1;i<=r;i++)
		cin >> U[i] >> V[i] >> W[i];
	for(int i=1;i<=g;i++)
	{
		int k;
		cin >> k;
		++now;
		add(now,t,1,0);
		for(int j=1;j<=k;j++)
		{
			int x;
			cin >> x;
			add(x,now,1,0);
		}
	}
	MCMF();
	if(maxflow!=g)
	{
		cout << -1;
		return 0;
	}
	for(int i=1;i<=r;i++)
	{
		int u=U[i],v=V[i],w=W[i];
		++now;
		add(now,t,1,w);
		add(u,now,1,0);
		add(v,now,1,0);
	}
	MCMF();
	if(maxflow!=n)
	{
		cout << -1;
		return 0;
	}
	printf("%d",mincost);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 16680kb

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: 15620kb

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: -100
Wrong Answer
time: 9ms
memory: 16240kb

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:

523

result:

wrong answer expected '526', found '523'