全球建站,微商代理网,百度指数的作用,wordpress换页正题
题目链接:https://www.luogu.com.cn/problem/AT5147 题目大意
有nnn个点的一张图#xff0c;其中i→i1(in)i\rightarrow i1(i n)i→i1(in)有一条边权值为000。
对于其他i,j(i≠j)i,j(i\neq j)i,j(ij)存在一条边i→ji\rightarrow ji→j#xff0c;若i其中i→i1(in)i\rightarrow i1(i n)i→i1(in)有一条边权值为000。
对于其他i,j(i≠j)i,j(i\neq j)i,j(ij)存在一条边i→ji\rightarrow ji→j若ijijij那么权值为−1-1−1否则为111。
删除i→j(i≠j)i\rightarrow j(i\neq j)i→j(ij)的代价为ai,ja_{i,j}ai,j要求代价最小的情况下使得图中不存在负环。
1≤n≤5001\leq n\leq 5001≤n≤500 解题思路
这个容易负环让人一头雾水不知道怎么维护我们知道差分约束有解的条件就是没有负环所以我们可以考虑转成差分约束模型。
那么对于不能删除的边i→i1i\rightarrow i1i→i1就有限制xi≥xi1x_i\geq x_{i1}xi≥xi1也就是整个序列单调不升。
然后形如i→j(ij)i\rightarrow j(ij)i→j(ij)可以视为xi−1≥xjx_i-1\geq x_jxi−1≥xj。 形如i←j(ij)i\leftarrow j(ij)i←j(ij)可以视为xi≤xj1x_i\leq x_j1xi≤xj1。
也就是xi−xj≤1x_i-x_j\leq 1xi−xj≤1和xi−xj≥1x_i-x_j\geq 1xi−xj≥1的限制我们考虑维护差分数组反过来的yixi−1−xiy_ix_{i-1}-x_{i}yixi−1−xi那么条件就是区间和不能大于/小于111显然的那么yiy_iyi就只有可能是0/10/10/1。
然后仔细观察这个限制会发现其实只有相邻的111会有用我们考虑dpdpdp来处理设fi,j,kf_{i,j,k}fi,j,k表示做到第iii个上一个111在jjj处再上一个111在kkk处。
前缀和一下aaa数组优化转移即可。
时间复杂度O(n3)O(n^3)O(n3) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N510;
ll n,a[N][N],s[N][N],t[N][N],f[N][N],ans;
signed main()
{scanf(%lld,n);for(ll i1;in;i)for(ll j1;jn;j){if(ij)continue;scanf(%lld,a[i][j]);}for(ll i1;in;i)for(ll j1;ji;j)s[i][j]s[i][j-1]a[j][i],t[i][j]t[i][j-1]a[i][j];memset(f,0x3f,sizeof(f));ansf[0][0];f[1][1]0;for(ll i2;in;i){for(ll j1;ji;j)for(ll k1;kj-(j!1);k)f[i][j]min(f[i][j],f[j][k]);for(ll j1;ji;j)for(ll k1;kj-(j!1);k)f[j][k]s[i][i]-s[i][j-1],f[j][k]t[i][k-1];}for(ll i1;in;i)for(ll j1;jn;j)ansmin(ans,f[i][j]);printf(%lld\n,ans);return 0;
}
