AtCoder AGC036D Negative Cycle (图论、DP)

题目链接

https://atcoder.jp/contests/agc036/tasks/agc036_d

题解

这都是怎么想出来的啊。。目瞪口呆系列。。

第一步转化至关重要: 一张图中不存在负环意味着什么？

不存在负环就存在最短路，我们可以给每个点分配一个权值\(p_i\)(相当于从\(1\)号到该点的最短路，点从\(1\)开始标号)满足对于任何边\((i,j)\)有\(p_j\ge p_i+w(i,j)\).

然后我们令\(q_i=p_i-p_{i+1}\), 那么由于边权都是\(1\)或者\(-1\)并且存在不能删的\(0\)边, 显然有\(q\)数组的值都是\(0\)或者\(1\).

约束变成了: 对于每条边\((i,j)\ (i>j)\)有\(\sum^{i-1}_{k=i}q_k\le 1\), 对于每条边\((i,j)\ (i<j)\)有\(\sum^{j-1}_{k=i}q_k\ge 1\).

所以问题就被转化成了: 你要给每个\(1\)到\((n-1)\)中的点\(q_i\)分配一个\(0\)或者\(1\)的权值，再删掉所有不满足约束条件的边，使得总代价最小！

天哪，这也太神仙了吧……

然后就是一个很容易的DP了，设\(dp[i][j]\)表示安排好前\(i\)位的\(q\)值，且强行令\(q_i=1\), 上一个为\(1\)的位置是\(j\)

那么考虑枚举\(k\), \(dp[i][j]\)转移到\(dp[k][i]\)，同时删去不合法的边

对于\(a>b\)的边\((a,b)\), 要删掉所有满足\(j<b\le i<x<a\)的边

对于\(a<b\)的边\((a,b)\), 要删掉所有满足\(j<i<a<b\le x\)的边

然后这个很容易使用二维前缀和优化，时间复杂度\(O(n^3)\).

啊啊啊人类智慧……

代码

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cassert>

#include<iostream>

#define llong long long

using namespace std;

inline int read()

{

	int x=0; bool f=1; char c=getchar();

	for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

	for(; isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^'0');

	if(f) return x;

	return -x;

}

const int N = 500;

llong a[N+3][N+3];

llong s[2][N+3][N+3];

llong dp[N+3][N+3];

int n;

void update(llong &x,llong y) {x = x<y?x:y;}

llong getsum(int typ,int lx,int rx,int ly,int ry)

{

	return s[typ][rx][ry]-s[typ][lx-1][ry]-s[typ][rx][ly-1]+s[typ][lx-1][ly-1];

}

int main()

{

	scanf("%d",&n);

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=n; j++)

		{

			if(j==i) continue;

			scanf("%lld",&a[i][j]);

		}

	}

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=n; j++)

		{

			if(i<j) {s[0][i][j] = a[i][j];}

			s[0][i][j] += s[0][i][j-1];

		}

		for(int j=1; j<=n; j++) s[0][i][j] += s[0][i-1][j];

	}

	for(int i=1; i<=n; i++)

	{

		for(int j=1; j<=n; j++)

		{

			if(i>j) {s[1][i][j] = a[i][j];}

			s[1][i][j] += s[1][i][j-1];

		}

		for(int j=1; j<=n; j++) s[1][i][j] += s[1][i-1][j];

	}

	memset(dp,42,sizeof(dp));

	dp[0][0] = 0ll;

	for(int i=0; i<=n; i++)

	{

		for(int j=0; j<max(i,1); j++)

		{

			for(int k=i+1; k<=n; k++)

			{

				llong tmp = dp[i][j]+getsum(1,k+1,n,j+1,i)+getsum(0,i+1,k,i+1,k);

				update(dp[k][i],tmp);

			}

		}

	}

	llong ans = dp[n][1];

	for(int i=1; i<=n; i++) update(ans,dp[n][i]);

	printf("%lld\n",ans);

	return 0;

}

巴特西

AtCoder AGC036D Negative Cycle (图论、DP)

题目链接

题解

代码

最新文章

热门文章