UVA 1658 海军上将(拆点法+最小费用限制流)

时间：2024-01-16 12:36:02

海军上将

紫书P375 这题我觉得有2个难点：

一是拆点，要有足够的想法才能把这题用网络流建模，并且知道如何拆点。

二是最小费用限制流，最小费用最大流我们都会，但如果限制流必须为一个值呢？比如这题限制这个流必须是2，我是不会的，所以应该灵活运用模板，并理解其中的道理。

【题目链接】海军上将

【题目类型】拆点法+最小费用限制流

&题解：

拆点，把中间的点拆为i和i'点，连线，cap为1，求最小费用流，且流限制为2，最终cost就是答案。

&代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int INF = 0x3f3f3f3f;

#define cle(a,val) memset(a,(val),sizeof(a))

#define SI(N) scanf("%d",&(N))

#define SII(N,M) scanf("%d %d",&(N),&(M))

#define SIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))

#define rep(i,b) for(int i=0;i<(b);i++)

#define rez(i,a,b) for(int i=(a);i<=(b);i++)

#define red(i,a,b) for(int i=(a);i>=(b);i--)

const ll LINF = 0x3f3f3f3f3f3f3f3f;

#define PU(x) puts(#x);

#define PI(A) cout<<(A)<<endl;

#define DG(x) cout<<#x<<"="<<(x)<<endl;

#define DGG(x,y) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<endl;

#define DGGG(x,y,z) cout<<#x<<"="<<(x)<<" "<<#y<<"="<<(y)<<" "<<#z<<"="<<(z)<<endl;

#define PIar(a,n) rep(i,n)cout<<a[i]<<" ";cout<<endl;

#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<" ";cout<<endl;}

const double EPS = 1e-9 ;

/*  ////////////////////////   C o d i n g  S p a c e   ////////////////////////  */

const int maxn = 2000 + 50 ;

struct Edge{

	int from,to,cap,flow,cost;

};

struct MCMF{

	int n;

	vector<Edge> edges;

	vector<int> G[maxn];

	int a[maxn];

	int p[maxn];

	int inq[maxn];

	int d[maxn];

	void init(int n){

		this->n=n;

		for(int i=0;i<n;i++)

			G[i].clear();

		edges.clear();

	}

	void AddEdge(int from,int to,int cap,int cost){

		edges.push_back((Edge){from,to,cap,0,cost});

		edges.push_back((Edge){to,from,0,0,-cost});

		int m=edges.size();

		G[from].push_back(m-2);

		G[to].push_back(m-1);

	}

	bool BellmanFord(int s,int t,int flow_limit,int& flow,long long& cost){

		for (int i=0;i<n;i++)

			d[i]=INF;

		memset(inq,0,sizeof(inq));

		d[s]=0; inq[s]=1; p[s]=0; a[s]=INF;

		queue<int> Q;

		Q.push(s);

		while(!Q.empty()){

			int x=Q.front(); Q.pop();

			inq[x]=0;

			for(int i=0;i<G[x].size();i++){

				Edge& e=edges[G[x][i]];

				if (e.cap>e.flow&&d[e.to]>d[x]+e.cost){

					a[e.to]=min(a[x],e.cap-e.flow);

					p[e.to]=G[x][i];

					d[e.to]=d[x]+e.cost;

					if (!inq[e.to]){

						Q.push(e.to);

						inq[e.to]=1;

					}

				}

			}

		}

		if (d[t]==INF) return false;

		//这里要限制flow 当大于我们想要的flow_limit时，就减小a[t]的值，使a[t]+flow正好等于flow_limit，所以a[t]应该减小为flow_limit-flow

		if (a[t]+flow>flow_limit) a[t]=flow_limit-flow;

		flow+=a[t];

		cost+=(long long)d[t]*(long long)a[t];

		for(int u=t;u!=s;u=edges[p[u]].from){

			edges[p[u]].flow+=a[t];

			edges[p[u]^1].flow-=a[t];

		}

		return true;

	}

	int MincostMaxflow(int s,int t,int flow_limit,long long& cost){

		int flow=0; cost=0;

		//这里也要加上限制 只有flow<flow_limit才继续，如果等于，就直接退出

		while(flow<flow_limit&&BellmanFord(s,t,flow_limit,flow,cost));

		return flow;

	}

};

MCMF g;

int n,m;

void Solve()

{

	while(cin>>n>>m){

		if (n==0) break;

		g.init(2*n-2);

		//拆点连边注意顺序

		for (int i=2;i<=n-1;i++){

			g.AddEdge(i-1,i+n-1-1,1,0);

		}

		while(m--){

			int a,b,c;

			//code从0开始 所以输入要减1 并且已经进行了拆点，所以输入连边时 注意是a连b，还是a'连b！！

			cin>>a>>b>>c;

			if (a!=1&&a!=n) a+=n-1 -1; else a--;

			b--;

			g.AddEdge(a,b,1,c);

		}

		long long cost;

		g.MincostMaxflow(0,n-1,2,cost);

		cout<<cost<<endl;

	}

}

int main()

{

    Solve();

    return 0;

}

相关文章