[COGS 741]负载平衡

这个网络流题挺简单的……

首先从[tex]S[/tex]向每个点连容量为该点存货量的边(费用为0)。首先注意最后所有存货量都要变成总的平均值,所以要从每个点向[tex]T[/tex]连一条容量为总的平均值的边(费用为0)。最后根据题目要求在相邻点之间连边(容量都是无限大,费用为1)。

跑一遍最小费用最大流,得出的费用就是答案。

代码:

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=110;
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);
    }
    int a[maxn];
    bool inQueue[maxn];
    int d[maxn],p[maxn];
    bool BellmanFord(int s,int t,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;
        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){
        register long long ans=0;
        while(BellmanFord(s,t,ans));
        return ans;
    }
};

int A[maxn];
int main(){
	register int i,ave=0;
	int n;
	freopen("overload.in","r",stdin);
	freopen("overload.out","w+",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&A[i]);
		ave+=A[i];
		MCMF::AddEdge(0,i,A[i],0);
	}
	ave/=n;
	for(i=1;i<=n;i++){
		MCMF::AddEdge(i,n+1,ave,0);
		if(i>1){
			MCMF::AddEdge(i-1,i,0x7f7f7f7f,1);
			MCMF::AddEdge(i,i-1,0x7f7f7f7f,1);
		}
		if(i<n){
			MCMF::AddEdge(i+1,i,0x7f7f7f7f,1);
			MCMF::AddEdge(i,i+1,0x7f7f7f7f,1);
		}
	}
	MCMF::AddEdge(1,n,0x7f7f7f7f,1);
	MCMF::AddEdge(n,1,0x7f7f7f7f,1);
	printf("%lld\n",MCMF::MincostMaxflow(0,n+1));
	fclose(stdin);
	fclose(stdout);
	return 0;
}

[BZOJ 1520]Szk-Schools

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

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

代码:

/**************************************************************
    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;
}

[COGS 740]分配问题

很明显是二分图最大权匹配。可以用匈牙利算法求解,但我比较弱……所以就写了个费用流。

注意最优解和最差解都要给出!

代码:

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=205;
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,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;
		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){
		register long long ans=0;
		while(BellmanFord(s,t,ans));
		return ans;
	}
};
int A[105][105];
int main(){
	int n;
	register int i,j;
	freopen("job.in","r",stdin);
	freopen("job.out","w+",stdout);
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			scanf("%d",&A[i][j]);
			MCMF::AddEdge(i,j+n,1,A[i][j]);
		}
	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);
	printf("%lld\n",MCMF::MincostMaxflow(0,2*n+1));
	MCMF::ClearGraph();
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++){
			MCMF::AddEdge(i,j+n,1,-A[i][j]);
		}
	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);
	printf("%lld\n",-(MCMF::MincostMaxflow(0,2*n+1)));
	return 0;
}