結果

問題 No.2320 Game World for PvP
ユーザー no wayno way
提出日時 2023-05-26 23:26:30
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 1,651 bytes
コンパイル時間 1,686 ms
コンパイル使用メモリ 170,560 KB
実行使用メモリ 4,380 KB
最終ジャッジ日時 2023-08-26 13:51:55
合計ジャッジ時間 2,926 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 2 ms
4,376 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 AC 2 ms
4,380 KB
testcase_04 AC 2 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 2 ms
4,376 KB
testcase_07 AC 2 ms
4,376 KB
testcase_08 AC 2 ms
4,376 KB
testcase_09 AC 2 ms
4,376 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 3 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 2 ms
4,376 KB
testcase_14 AC 3 ms
4,376 KB
testcase_15 AC 2 ms
4,380 KB
testcase_16 AC 2 ms
4,376 KB
testcase_17 AC 2 ms
4,380 KB
testcase_18 AC 3 ms
4,380 KB
testcase_19 AC 3 ms
4,376 KB
testcase_20 AC 3 ms
4,380 KB
testcase_21 AC 2 ms
4,380 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 3 ms
4,380 KB
testcase_24 AC 2 ms
4,376 KB
testcase_25 AC 2 ms
4,376 KB
testcase_26 AC 3 ms
4,380 KB
testcase_27 AC 1 ms
4,376 KB
testcase_28 AC 4 ms
4,380 KB
testcase_29 AC 3 ms
4,376 KB
testcase_30 AC 3 ms
4,376 KB
testcase_31 AC 4 ms
4,376 KB
testcase_32 AC 2 ms
4,376 KB
testcase_33 AC 4 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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());
}
0