danihao123

搜索

音乐播放器

RSS

RSS Link

计数器

26239

[BZOJ 1520]Szk-Schools

2016年9月04日 15:53 | Comments(0) | Category:题解 | Tags:

这个是二分图最小权完美匹配啦……不过我还是写的费用流。

不过注意一定要判断是否有完美匹配。

代码:

/**************************************************************
    Problem: 1520
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2016 ms
    Memory:5004 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=410;
namespace MCMF{
    struct Edge{
        int u,v,cap,flow,cost;
    };
    vector<Edge> edges;
    vector<int> G[maxn];
    int m;
    inline void AddEdge(int u,int v,int cap,int cost){
        edges.push_back((Edge){u,v,cap,0,cost});
        edges.push_back((Edge){v,u,0,0,-cost});
        m=edges.size();
        G[u].push_back(m-2);
        G[v].push_back(m-1);
    }
    inline void ClearGraph(){
        register int i;
        edges.clear();
        for(i=0;i<maxn;i++)
            G[i].clear();
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,int& flow,long long& cost){
        register int i,u;
        queue<int> Q;
        memset(d,0x7f,sizeof(d));
        memset(inQueue,0,sizeof(inQueue));
        d[s]=0;
        inQueue[s]=true;
        p[s]=0;
        a[s]=0x7f7f7f7f;
        Q.push(s);
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow && d[e.v]>d[u]+e.cost){
                    d[e.v]=d[u]+e.cost;
                    p[e.v]=G[u][i];
                    a[e.v]=min(a[u],e.cap-e.flow);
                    if(!inQueue[e.v]){
                        Q.push(e.v);
                        inQueue[e.v]=true;
                    }
                }
            }
        }
        if(d[t]==0x7f7f7f7f)
            return false;
        flow+=a[t];
        cost+=((long long)d[t])*((long long)a[t]);
        for(u=t;u!=s;u=edges[p[u]].u){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    long long MincostMaxflow(int s,int t,int& flow){
        register long long ans=0;
        while(BellmanFord(s,t,flow,ans));
        return ans;
    }
};
int main(){
    int n,m,a,b,k;
    register int i,j,cost,flow=0;
    register long long ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%d%d%d%d",&m,&a,&b,&k);
        for(j=a;j<=b;j++){
            cost=k*abs(j-m);
            MCMF::AddEdge(i,j+n,1,cost);
        }
    }
    for(i=1;i<=n;i++)
        MCMF::AddEdge(0,i,1,0);
    for(i=n+1;i<=2*n;i++)
        MCMF::AddEdge(i,2*n+1,1,0);
    ans=MCMF::MincostMaxflow(0,2*n+1,flow);
    if(flow<n)
        puts("NIE");
    else
        printf("%lld\n",ans);
    return 0;
}