QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#25422 | #1825. The King's Guards | conqueror_of_zky | WA | 4ms | 18052kb | C++14 | 2.3kb | 2022-04-03 18:11:39 | 2022-04-29 01:25:40 |
Judging History
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,-10000000);
for(int j=1;j<=k;j++)
{
int x;
cin >> x;
add(x,now,1,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();
mincost+=10000000*g;
if(maxflow!=n||mincost>1e6)
{
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: 15636kb
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: 4ms
memory: 18052kb
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: 3ms
memory: 17812kb
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'