$$\color{Purple}{kuangbin题解目录}$$
描述
给定一个 $n \\times n$ 的矩阵 $C_{ij}$($1 \\le i,j \\le n$)。
我们想找到一个 $n \\times n$ 的 $01$ 矩阵 $X_{ij}$($1 \\le i,j \\le n$)。
$X_{ij}$ 应满足以下条件:
- $X_{12}+X_{13}+…+X_{1n}=1$。
- $X_{1n}+X_{2n}+…X_{n-1n}=1$。
- 对于每个 $i$($1 < i < n$),满足 $∑X_{ki} (1 \\le k \\le n)=∑X_{ij} (1 \\le j \\le n)$。
例如,当 $n=4$ 时,需满足:
- $X_{12}+X_{13}+X_{14}=1$
- $X_{14}+X_{24}+X_{34}=1$
- $X_{12}+X_{22}+X_{32}+X_{42}=X_{21}+X_{22}+X_{23}+X_{24}$
- $X_{13}+X_{23}+X_{33}+X_{43}=X_{31}+X_{32}+X_{33}+X_{34}$
现在,我们想知道你能得到的 $∑C_{ij} \\times X_{ij}(1 \\le i,j \\le n)$ 的最小值。
输入格式
输入包含多组测试数据。
每组数据第一行包含整数 $n$。
接下来 $n$ 行,每行 $n$ 个整数,用来描述矩阵 $C_{ij}$。
输出格式
每个测试数据输出一行结果,表示你能得到的 $∑C_{ij} \\times X_{ij}(1 \\le i,j \\le n)$ 的最小值。
数据范围
输入最多包含 $35$ 组数据。
$2 \\le n \\le 300$,
$0 \\le C_{ij} \\le 10^5$。
输入样例:
4
1 2 4 10
2 0 1 1
2 2 0 5
6 3 1 2
输出样例:
3
思路
- 式子$1$: $X_{12}+X_{13}+…+X_{1n}=1$,可转化为$\sum_{k=2}^{n}{X_{1(k)}}=1$,表示
起始点
$1$到其余每个点中的任意一个点
可以有一条边
,起始点$1$的出度
为$1$.- 式子$2$: $X_{1n}+X_{2n}+…X_{(n-1)n}=1$,可转化为$\sum_{k=1}^{n-1}{X_{(k)n}}=1$,表示
其余每一个点中的中任意一个
点到终点
($n$)可以有一条边
,终点($n$)的入度
为$1$.- 式子$3$: 对于每个 $i$($1 < i < n$),满足 $∑X_{ki} (1 \\le k \\le n)=∑X_{ij} (1 \\le j \\le n)$,其中前半部分$∑X_{ki} (1 \\le k \\le n)$表示除
起始点
$1$和终点
($n$)的剩余点
$i$中,从点$k$到点$i$的入度和
,同理,后半部分$∑X_{ij} (1 \\le j \\le n)$表示除起始点
$1$和终点
($n$)的剩余点
$i$中,从点$i$到点$j$的出度和
,总结可得,除起始点
$1$和终点
($n$)的每个点
的出入度相同
.
- 已知$C_{ij}$,并且知道$X_{ij}$为$01$矩阵且满足上述三个式子,最终求$∑C_{ij} \\times X_{ij}(1 \\le i,j \\le n)$ 的
最小值
,故在构造的$01$矩阵$X$中,$0$的个数越多,求得的结果必然越小;- 此时可将该$01$矩阵$X$转化为
图
,其中当$X_{ij}=1$表示在图中存在
一条从$i$到$j$的边,反之,则不存在
该边;- 该问题有转化为求
点1到点n的最短距离
,此时满足上述三个式子点($1$的出度
为$1$,点$n$的入度
为$1$,其余点
的出入度写相等);
- 但是除了这种最短路的情况满足三个条件,还有一种情况也满足:
- 从点$1$出发经过
除点n的任意点
然后回到点1
的环路
;
- 从点$n$出发经过
除点1的任意点
然后回到点n
的环路
.- 两个
环路
构成的图刚好也满足三个条件,因此结果需在点1到点n的最短距离
与最小二环距离之和
中取较小值
;
- 故可采用
spfa算法
求最短路
,同时求最小环
.
代码
// Problem: 0或1
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4268/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-02-07 14:53:29
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#define MAXN 310
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n;
int C[MAXN][MAXN];
int dist[MAXN],vis[MAXN];
void spfa(int start)
{
memset(dist,0x3f,sizeof(dist));
memset(vis,0,sizeof(vis));
queue<int> q;
dist[start]=0;
vis[start]=1;
q.push(start);
while(q.size()>0)
{
int temp=q.front();
q.pop();
vis[temp]=0;
for(int i=1;i<=n;i++)
if(dist[i]>dist[temp]+C[temp][i])
{
dist[i]=dist[temp]+C[temp][i];
if(vis[i]==0)
{
vis[i]=1;
q.push(i);
}
}
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
while(scanf("%d",&n)!=EOF)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&C[i][j]);
spfa(1);
int res=dist[n];//1-n的最短路径
//cout << res << endl;
int res1=inf,res2=inf;
for(int i=2;i<=n-1;i++)
res1=min(res1,dist[i]+C[i][1]);
spfa(n);
for(int i=2;i<=n-1;i++)
res2=min(res2,dist[i]+C[i][n]);
printf("%d\n",min(res,res1+res2));
}
return 0;
}