OrzPandaCup F(二次代价网络流，最优化)

wtcl，验个题debug了一整天才对

题意

给定n(1<=n<=50)个点，m(0<=m<=200)条边的无向图，边权为ci。每个点需要获得数量不等的水，数量为wi。有k个源点，源点的产水量是无限的。可以通过管道将水运送到另一个节点。通过管道i的流量为fi时，代价为$f_i^2\times c_i$。问最小代价，若无解输出-1。

验题题解

由于代价为二次，而且流量可以不为整数，感觉跟网络流模型的关系不大。因此直接考虑数学上的最优化。对每个管道设一个有向流量fi作为变量，则目标就是使他们的加权平方和最小。对于非源端的节点，流量平衡条件是一个线性的等式约束。而对于源点，会出现不等约束。但是本题中，源点自身的消耗不会对答案做出贡献，也不可能从其他地方输入水，这说明对源点的约束是完全没有必要的，可以直接排除。

$$\min_{f_i} \sum f_i^2\times c_i \ \mathrm{s.t.} \sum_{f_j\in edgeof(v_i)}f_j=w_i, \text{where }v_i\text{is not source vertex}$$

然后对它做拉格朗日乘子法，会得到一个线性方程组，直接使用高斯消元求解。线性方程组的变量为流量fi和拉格朗日乘子，每个变量都对应一条方程。经过分析，某些情况下该方程组可能会无解或者多解。无解情况说明约束本身不满足，例如一个连通块里连个水源都没有。如果出现多解，说明这条边的流量不影响答案，例如权值为0的边连接源点的通路。

注意代码考虑到重边、自环等细节的影响。

代码

```
    #include <bits/stdc++.h>
```
```
    using namespace std;
```
```
 
```

    #define inc(i,n) for(int i=0;i<n;i++)

```
    typedef double db;
```
```
    db w[50];
```

    int sp[50],nsp[50]; bool source[50];

```
 
```
```
    const db eps=1e-9;
```
```
    const int maxn=300,maxm=300;
```
```
    db a[maxn][maxm],ans[maxn],cc[300];
```
```
    int N,M;
```
```
 
```

    //Ax=b where A is any shape of augmented matrix

    //not require m=n+1, get a possible solution ans[0..m-1)

```
    bool gauss_solve_possible(){
```
```
    	M=N+1;
```
```
    	int l=0; //real line
```
```
    	inc(i,M){ //i: col start pos
```
```
    		int maxl=l;
```
```
    		for (int j=l;j<N;j++)
```

    			if (fabs(a[j][i])>fabs(a[maxl][i])) maxl=j;

```
    		if (maxl!=l) swap(a[l],a[maxl]);
```
```
    		if (fabs(a[l][i])<eps)
```

    			continue; //no solution or infinity solution, next col

```
    		for (int j=l+1;j<N;j++){
```
```
    			db r=a[j][i]/a[l][i];
```
```
    			for (int k=i;k<M;k++)
```
```
    				a[j][k]-=r*a[l][k];
```
```
    		}
```
```
    		db r=a[l][i];
```
```
    		for (int k=i;k<M;k++) a[l][k]/=r;
```
```
    		l++;
```
```
    	} //now l is rank of matrix
```
```
    	int last=M-1,cur;
```
```
    	for (int i=l-1;i>=0;i--){
```

    		for (cur=0;cur<M-1 && fabs(a[i][cur])<eps;cur++); //first no zero column

```
    		db t=a[i][M-1];
```

    		for (int j=last;j<M-1;j++) t=t-a[i][j]*ans[j];

    		for (last--;last>cur;last--) //any solution, set to 0

    			ans[last]=0;  //,t=(t-a[i][j]*ans[last]%p+p)%p; when ans[last] is not 0

    		if (cur==M-1 && fabs(t)>eps) return 0; //detected 0*x!=0, no solu

```
    		ans[cur]=t;
```
```
    		last=cur;
```
```
    	}
```
```
    	return 1;
```
```
    }
```
```
 
```
```
    int main(){
```
```
    	int n,m,K,x,y,c,t; cin>>n>>m>>K;
```
```
    	inc(i,n) cin>>w[i];
```
```
    	inc(i,K) {
```
```
    		cin>>sp[i],sp[i]--;
```
```
    		source[sp[i]]=1;
```
```
    	}
```

    	t=0; inc(i,n) if (!source[i]) nsp[i]=t++; //Lagrange multiplier

```
    	N=m+t; //dim
```
```
    	inc(i,m){
```
```
    		cin>>x>>y>>c;
```
```
    		cc[i]=c; x--;y--;
```
```
    		if (x==y) continue;
```
```
    		a[i][i]=2*c;
```

    		if (!source[x]) a[i][m+nsp[x]]=1,a[m+nsp[x]][i]=-1;

    		if (!source[y]) a[i][m+nsp[y]]=-1,a[m+nsp[y]][i]=1;

```
    	}
```

    	inc(i,n) if (!source[i]) a[m+nsp[i]][N]=w[i];

```
    	db sum=0;
```

    	if (!gauss_solve_possible()) return 0*puts("-1");

```
    	else
```
```
    		inc(i,m)
```
```
    			sum+=ans[i]*ans[i]*cc[i];
```
```
    	printf("%.10f\n",sum);
```
```
    	return 0;
```
```
    }
```

fffasttime

OrzPandaCup F(二次代价网络流，最优化)

题意

验题题解

代码

发表评论取消回复

题意

验题题解

代码

发表评论 取消回复

发表评论取消回复