SCOI2011 糖果

题目:

  幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

思路:

  根据题意不难想到差分约束。根据题目给的条件建出图后,第一种想法是直接spfa判正环和求最长路,第二种做法借助边权只有,用缩点和DAG上的dp解决,这里只写第二种的思路(第一种好像也没什么好写的啊)
  在整个图上缩点后,如果一个强联通块中存在一条权值为,直接就无解。剩下的情况就是所有的强联通块中的都是,那么这些强联通块都可以看做一个点(只要在算糖果数时乘上点的个数),在DAG上一次dp就能算出最长路了。
  upd:学弟找到另一种判负环的方法,记录每个点被到达的边数,如果超过就说明有环,貌似快了一些。。

代码:

  • 缩点加dp:
#include <bits/stdc++.h>
#define MN 100010
#define clr(a,b) memset(a,b,sizeof a)
#define inf 2100000000
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
struct Edge{int to,w;};
Link<MN,MN*3,Edge> G,M;
void addEdge(int u,int v,int d){G.add(u,(Edge){v,d});}
int dfn[MN],low[MN],siz[MN],ble[MN],stk[MN],tp,No,bcnt;
void dfs(int o){
    dfn[o]=low[o]=++No;
    stk[++tp]=o;
    EOR(k,G,o){
        Edge e=G[k];
        if(!dfn[e.to]){
            dfs(e.to);
            tomin(low[o],low[e.to]);
        }
        else if(!ble[e.to])tomin(low[o],dfn[e.to]);
    }
    if(dfn[o]==low[o]){
        bcnt++;
        do {
            ble[stk[tp]]=bcnt;
            siz[bcnt]++;
        }while(stk[tp--]!=o);
    }
}
int ind[MN],n;
bool No_Ans;
void rebuild(){
    FOR(o,0,n)EOR(k,G,o){
        int v=G[k].to,w=G[k].w;
        if(ble[v]!=ble[o]){
            M.add(ble[o],(Edge){ble[v],w});
            ind[ble[v]]++;
        }
        else if(w)No_Ans=1;
    }
}
#define ll long long
ll ans=0;
void solve(){
    static int Q[MN],dp[MN];
    int hed=1,tai=0;
    Q[++tai]=ble[0];
    while(hed<=tai){
        int o=Q[hed++];
        EOR(k,M,o){
            int v=M[k].to;
            if(!--ind[v])Q[++tai]=v;
        }
    }
    clr(dp,0x8f);dp[Q[0]]=0;
    FOR(i,0,tai){
        int o=Q[i];
        EOR(k,M,o){
            Edge e=M[k];
            tomax(dp[e.to],dp[o]+e.w);
        }
    }
    FOR(i,1,n)ans+=(ll)siz[i]*dp[i];
}
int main(){
    int k,a,b,x;
    scanf("%d%d",&n,&k);
    while(k--){
        scanf("%d%d%d",&x,&a,&b);
        if(x==1){
            addEdge(a,b,0);
            addEdge(b,a,0);
        }
        else if(x==2)
            addEdge(a,b,1);
        else if(x==3)
            addEdge(b,a,0);
        else if(x==4)
            addEdge(b,a,1);
        else if(x==5)
            addEdge(a,b,0);
    }
    FOR(i,1,n)addEdge(0,i,1);
    FOR(i,1,n)if(!dfn[i])dfs(i);
    rebuild();
    if(No_Ans)puts("-1");
    else printf("%lld\n",(solve(),ans));
    return 0;
}
  • 最短路:
#include <bits/stdc++.h>
#define MN 100010
#define clr(a,b) memset(a,b,sizeof a)
#define inf 2100000000
#define FOR(i,a,b) for(int i=(a),i##END=(b);i<=i##END;i++)
#define DOR(i,a,b) for(int i=(a),i##END=(b);i>=i##END;i--)
using namespace std;
template<class T> bool tomin(T &a,T b){return a>b?a=b,1:0;}
template<class T> bool tomax(T &a,T b){return a<b?a=b,1:0;}
template<int N,int M,class T> struct Link{
    int HEAD[N],NXT[M],tot;T W[M];
    void clear(){clr(HEAD,0);tot=0;}
    void add(int x,T w){NXT[++tot]=HEAD[x];W[HEAD[x]=tot]=w;}
    T& operator [] (int x){return W[x];}
    #define EOR(k,G,o) for(int k=G.HEAD[o];k;k=G.NXT[k])
};
struct Edge{int to,w;};
Link<MN,MN*3,Edge> G;
void addEdge(int a,int b,int c){G.add(a,(Edge){b,c});}
int dis[MN],inq[MN],cnt[MN],n;
deque<int> q;
bool spfa(int s){
    clr(dis,0x8f);clr(cnt,0);
    q.clear();clr(inq,0);
    q.push_back(s);inq[s]=1;
    dis[s]=0;
    while(!q.empty()){
        int o=q.front();q.pop_front();
        inq[o]=0;
        EOR(k,G,o){
            Edge e=G[k];
            if(tomax(dis[e.to],dis[o]+e.w)&&!inq[e.to]){
                inq[e.to]=1;
                if(q.empty()||dis[q.front()]<dis[e.to])
                    q.push_back(e.to);
                else
                    q.push_front(e.to);
                cnt[e.to]=cnt[o]+1;
                if(cnt[e.to]==n)return false;
            }
        }
    }
    return true;
}
int main(){
    int k,x,a,b;
//    freopen("data.txt","r",stdin);
    scanf("%d%d",&n,&k);
    while(k--){
        scanf("%d%d%d",&x,&a,&b);
        if(x==1){
            addEdge(a,b,0);
            addEdge(b,a,0);
        }
        else if(x==2)
            addEdge(a,b,1);
        else if(x==3)
            addEdge(b,a,0);
        else if(x==4)
            addEdge(b,a,1);
        else if(x==5)
            addEdge(a,b,0);
    }
    FOR(i,1,n)addEdge(n+1,i,1);
    long long ans=0;
    if(!spfa(n+1))puts("-1");
    else {
        FOR(i,1,n)ans+=dis[i];
        printf("%lld\n",ans);
    }
    return 0;
}