Dij+EK费用流

Dij+EK

因为Dij不能运行在负权图上，所以要进行一些处理。

我们对网络\(G\)中的每个点i设置一个势函数\(h[i]\)，在算法运行的每一时刻，对于每条残余网络中的边\((u, v)\)，都要满足\(h[u] + w[u][v] – h[u] >= 0\)，设L为原图\(S\)\(到\)\(T\)路的长度，那么现在\(S\)到\(T\)最短路为\(L'=h[S]+L-h[T]\)，最优化L与最优化L'是等价的，所以可以用这种方法维护。

用\(w'\)表示现在图的边权,\(dis'\)表示到当前点的最短距离。某次增广结束后，边\((j, i)\)被加。

满足\(dis’[i] + w’[i][j] = dis’[j]\)

那么 \(dis’[i] + w[i][j] + h[i] – h[j] = dis’[j]\)

​ \((dis’[j] + h[j]) - (dis’[i] + h[i]) – w[i][j] = 0\)

​ \((d’[j] + h[j]) - (d’[i] + h[i]) + w[j][i] = 0\)

仍然满足势能函数性质。

对于边(i,j)，有\((d’[i] + h[i]) - (d’[j] + h[j]) + w[i][j] >= 0\)

仍然满足性质。

P3705 [SDOI2017]新生舞会

显然分数规划，边权连\(a[i]-b[i]*mid\)，然后跑最大费用最大流就行了。

#include<bits/stdc++.h>
using namespace std;
#define INF 1000000000.0
#define int long long
//#define double long double
const int MAXN=5e3+5,M=2e5+5;
struct Node{
	int to,nxt;
	double cost,val;
};
Node G[M];
int head[M],tot=1;
void addedge(int from,int to,double flow,double dis) {
	G[++tot].nxt=head[from];
	G[tot].to=to;
	G[tot].cost=dis;
	G[tot].val=flow;
	head[from]=tot;
}
int dep[MAXN],V[MAXN],E[MAXN];
bool inque[MAXN];
double dis[MAXN],h[MAXN],a[1005][1005],b[1005][1005];
int vis[MAXN];
int n,m,s,t;
long double ans;
long double res;
bool dijkstra(){
	for(int i=0;i<=t;i++) dis[i]=INF;	
	memset(vis,0,sizeof vis);	
	dis[s]=0;	
	memset(V,0,sizeof(V));
	memset(E,0,sizeof(E));
	priority_queue<pair<double,int>,vector<pair<double,int> >,greater<pair<double,int> > > q;
	q.push({0,s});
	while(q.size()){
		int u=q.top().second;	
		q.pop();
		if(vis[u]) continue;	
		vis[u]=1;
		for(int i=head[u];i;i=G[i].nxt){
			int v=G[i].to;
			if(G[i].val&&dis[v]>dis[u]+G[i].cost+h[u]-h[v]){
				dis[v]=dis[u]+G[i].cost+h[u]-h[v];
				V[v]=u; E[v]=i;	q.push({dis[v],v});
			}
		}
	}
	for(int i=s;i<=t;i++)	
		if(dis[i]<INF)
		h[i]+=dis[i];
	return dis[t]!=INF;
}
void EK(){
	while(dijkstra()){	
		double mi=INF;
		for(int i=t;i!=s;i=V[i]) mi=min(mi,G[E[i]].val);
		for(int i=t;i!=s;i=V[i]) G[E[i]].val-=mi,G[E[i]^1ll].val+=mi;
		res+=h[t]*1.0*mi,ans+=mi;
	}
}
bool check(double mid){
	tot=1;
	memset(head,-1,sizeof(head));
	memset(h,0,sizeof(h));
	s=0;t=n*2+1;
	for(int i=1;i<=n;i++){
		addedge(s,i,1,0);
		addedge(i,s,0,0);
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			addedge(i,j+n,1,-a[i][j]+mid*b[i][j]);
			addedge(j+n,i,0,a[i][j]-mid*b[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		addedge(i+n,t,1,0);
		addedge(t,i+n,0,0);
	}
	res = 0;
	ans=0;
	EK();
	if(res<0) return 1;
	return 0;
}
signed main(){
	int A, B, C, D;
	scanf("%lld", &n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lf",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			scanf("%lf",&b[i][j]);
		}
	}
	long double l=0,r=10000,mid;
	while(l+1e-9<r){
		mid=(l+r)/2.0;
		if(check(mid)){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	printf("%.6Lf", l);
	return 0;
}