E - Capitalism(求差值最大。”=“情况的差分约束)

题:https://codeforces.com/contest/1450/problem/E

题意:给定n点m边图,边:[u,v,d]当d为1时,a[v]-a[u]=1,当d为0时,|a[v]-a[u]|=0,求给a数组赋值,图关系合法且最大化max{ a[i] } - min{ a[i] }

分析:

  1. 差分约束”=“的情况,将d==1时的情况转化为a[v]-a[u]<=1, a[v]-a[u]>=1,所以cost[u][v]=1,cost[v][u]=-1。
  2. 同理,d==0时cost[u][v]=1,cost[v][u]=1, 求差值最大根据差分约束去跑最短路;
  3. ”NO“情况就判断有无负权环和判断路径是否合法,
E - Capitalism(求差值最大。”=“情况的差分约束)
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define UM unordered_map
typedef long long ll;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const ll INF=1e18;
#define pi 3.1415926535898
#define DEC (pi/180)
const int M=202;
int cost[M][M];
int u[M*10],v[M*10],d[M*10];
void py(){
    puts("YES");
}
void pn(){
    puts("NO");
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i!=j)
                cost[i][j]=inf;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u[i],&v[i],&d[i]);
        cost[u[i]][v[i]]=1;
        cost[v[i]][u[i]]=(d[i] == 1 ? -1 : 1);
    }
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j]);
            }
        }

    ///negative
    for(int i=1;i<=n;i++)
        if(cost[i][i]<0)
            return pn(),0;
    ///find max
    int pos=1,maxx=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(maxx<cost[i][j]){
                maxx=cost[i][j];
                pos=i;
            }
    ///judge legal
    for(int i=1;i<=m;i++)
        if(cost[pos][u[i]]==cost[pos][v[i]])
            return pn(),0;

    py();
    printf("%d\n",maxx);
    for(int i=1;i<=n;i++)
        printf("%d ",cost[pos][i]);
    return 0;
}
View Code

 

E - Capitalism(求差值最大。”=“情况的差分约束)

上一篇:windows下安装scrapy


下一篇:windows下的 长路径