結果
問題 | No.2320 Game World for PvP |
ユーザー |
|
提出日時 | 2023-05-26 23:26:30 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4 ms / 2,000 ms |
コード長 | 1,651 bytes |
コンパイル時間 | 1,563 ms |
コンパイル使用メモリ | 172,856 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-25 10:58:10 |
合計ジャッジ時間 | 2,609 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 |
ソースコード
#include<bits/stdc++.h>using namespace std;const int N=200;const long long inf=1e17;struct node{int u,to;long long w;}edge[N*N];int head[N],arrange[N],cur[N],a[N],b[N],p[N],c[N][N];int n,m,s,t,x,y,z,k,sx,tx;void add(int x,int y,long long z) {edge[k].u=y; edge[k].to=head[x]; edge[k].w=z; head[x]=k++;edge[k].u=x; edge[k].to=head[y]; edge[k].w=z; head[y]=k++;}bool bfs(){memset(arrange,0,sizeof(arrange));queue<int>q;q.push(s);arrange[s]=1;while (!q.empty()){int v=q.front(); q.pop(); if (t==v) return 1;for (int i=head[v];i!=-1;i=edge[i].to){int u=edge[i].u;if (arrange[u]||!edge[i].w) continue;arrange[u]=arrange[v]+1;q.push(u);}}return 0;}long long dfs(int now,long long maxlow,int t){if (now==t) return maxlow;long long ret=0;for (int &i=cur[now];i!=-1;i=edge[i].to){int u=edge[i].u;if (arrange[u]!=arrange[now]+1||!edge[i].w) continue;long long f=dfs(u,min(maxlow-ret,edge[i].w),t);edge[i].w-=f; edge[i^1].w+=f;ret+=f;if (f==maxlow) return maxlow;}return ret;}long long dinic(){long long ans=0;while (bfs()){memcpy(cur,head,sizeof(head));ans+=dfs(s,inf,t);}return ans;}int main(){scanf("%d%d%d",&n,&sx,&tx);memset(head,-1,sizeof(head));k=0;s=n+1,t=n+2;for (int i=1;i<=sx;i++){scanf("%d",&a[i]);p[a[i]]=1;add(s,a[i],inf);}for (int i=1;i<=tx;i++){scanf("%d",&b[i]);p[b[i]]=1;add(b[i],t,inf);}long long ans=0;for (int i=1;i<=n;i++)for (int j=1;j<=n;j++) scanf("%d",&c[i][j]),ans+=c[i][j];ans/=2;for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++) add(i,j,c[i][j]);printf("%lld\n",ans-dinic());}