以poj1752题为根源整理的差分约束的板子

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=5e5+50;
struct Edge{
    int u,v,w,next;
}E[maxn*4];
struct Node{
    int x,y;
}arr[maxn];
int cnt, head[maxn],maxs,mins;
int mp[maxn],id,rmp[maxn],c[maxn];
int pre[maxn];
string s;
void init(){
    cnt=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w){
    E[cnt].u=u;
    E[cnt].v=v;
    E[cnt].w=w;
    E[cnt].next=head[u];
    head[u]=cnt++;
}
int vis[maxn];
int tim[maxn];
int dist[maxn];
int SPFA(int n,int s){
    queue <int> que;
    memset(dist,-inf,sizeof(dist));
    memset(tim,0,sizeof(tim));
    memset(vis,0,sizeof(vis));
    que.push(s);
    dist[s]=0;
    tim[s]++;
    vis[s]=1;
    while(!que.empty()){
        int tp=que.front();
        que.pop();
        vis[tp]=0;
        for(int i=head[tp];~i;i=E[i].next){
            int v=E[i].v;
            if(dist[tp]+E[i].w>dist[v]){
                pre[v]=tp;
                dist[v]=dist[tp]+E[i].w;
                if(vis[v]==0){
                    vis[v]=1;
                    que.push(v);
                    if(++tim[v]>=n){
                        return 1;
                    }
                }
            }
        }
    }
    return 0;
}
int main(){
    int T,cas=1;
    int k,m;
    while(scanf("%d%d",&k,&m)!=EOF){
        init();maxs=-inf;
        for(int i=0;i<40000;i++)
            mp[i]=0;
        id=0;
        for(int i=1;i<=m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            if(x>y)
                swap(x,y);
            x--;
            x+=20000;
            y+=20000;
            arr[i].x=x;arr[i].y=y;
            if(!mp[x]){
                c[++id]=x;mp[x]=1;
            }
            if(!mp[y]){
                c[++id]=y;mp[y]=1;
            }
        }
        sort(c+1,c+1+id);
        for(int i=1;i<=id;i++){
            mp[c[i]]=i;
            if(i==1)
                continue;
            add(i-1,i,0);
            add(i,i-1,-c[i]+c[i-1]);
        }
        for(int i=1;i<=m;i++){
            int x=mp[arr[i].x],y=mp[arr[i].y];
            if(arr[i].y-arr[i].x>k){
                add(x,y,k);
                add(y,x,arr[i].x-arr[i].y);
            }else{
                add(x,y,arr[i].y-arr[i].x);
                add(y,x,-arr[i].y+arr[i].x);
            }
        }
        int n=id;
        pre[1]=-1;
        int ans=SPFA(n,1);
        printf("%d\n",dist[n]);
        for(int i=1;i<id;i++){
            int num=dist[i+1]-dist[i];
            for(int j=1;j<=num;j++){
                printf("%d\n",c[i]+j-20000);
            }
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注