最小有向树形图
1 无环
2 每个点入度为1
朱刘算法
1 贪心的从每个点的所有入边中找一条权值最小的边
2 从选出的边中判断是否存在环
2.1 不存在环,结束,把所有边权值加上作为答案
2.2 存在环,进入第3步
3 将所有环缩点,构造新图G',缩点前把所有边权值加上
3.1 环内的边 2->3 3->4 4->2
删去
3.2 终点在环内的边 1->4 1->2
权值 w' = w - 终点入边权值
w[1->4]' = w[1->4] - w[3->4] = 5 - 1 = 4
w[1->2]' = w[1->2] - w[4->2] = 4 - 2 = 2
3.3 其他边 4->5
不变
每次缩一次点,点数最少-1,所以总共最多迭代n次算法结束。
证明:
首先有性质:
1 环中的边一定至少要去掉一条边
2 ⭐ 一定存在一个最优解,只去一条边
假设去了两条环内边,则说明环内有两个点的入边权值变大
3 缩点前和缩点后的树形图的最小权值相等--则要求G的最小权和==G'的最小权和
任给G中的一个树形图一定能找到一种变换变换到对应的G'
任给G'中的一个树形图一定能找到对应的G
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef pair<double, double> PDD;//坐标 距离要开根号--double
const int N = 110;
const double INF = 1e8;
int n, m;
PDD q[N];
bool g[N][N];//邻接矩阵 相邻
double d[N][N], bd[N][N];// 距离 备份数组
int pre[N], bpre[N];// 入边 备份数组
int dfn[N], low[N], ts, stk[N], top;// tarjan dfn序 low数组 时间戳 栈 栈顶
int id[N], cnt;//缩点后新图
bool st[N], ins[N];//判断从1号点能不能搜到所有点
void dfs(int u)
{
st[u] = true;
for (int i = 1; i <= n; i ++ )
if (g[u][i] && !st[i])
dfs(i);
}
bool check_con()
{
memset(st, 0, sizeof st);
dfs(1);
for (int i = 1; i <= n; i ++ )
if (!st[i])
return false;
return true;
}
double get_dist(int a, int b)
{
double dx = q[a].x - q[b].x;
double dy = q[a].y - q[b].y;
return sqrt(dx * dx + dy * dy);
}
void tarjan(int u)
{
dfn[u] = low[u] = ++ts;
stk[++top]=u,ins[u]=true;
int j = pre[u];
if(!dfn[j])//没搜过 用low[j]更新low[u]
{
tarjan(j);
low[u] = min(low[j],low[u]);
}
else if(ins[j])//在栈里 用dfn[j]更新low[u]
{
low[u] = min(low[u],dfn[j]);
}
if(low[u]==dfn[u])//比u低的j都dfs完了之后回到u发现u是最高的,开始把比u低的j出栈
{
int y;
++cnt;
do
{
y=stk[top--],ins[y]=false,id[y]=cnt;
}while(y!=u);
}
}
double work()
{
double res = 0;
// 初始化距离矩阵
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (g[i][j]) d[i][j] = get_dist(i, j);
else d[i][j] = INF;
while (true)
{
// 求所有入边的最小值
for (int i = 1; i <= n; i ++ )
{
pre[i] = i;// 入边首先初始化为自己到自己的INF
for (int j = 1; j <= n; j ++ )
if (d[pre[i]][i] > d[j][i])
pre[i] = j;
}
// tarjan
memset(dfn, 0, sizeof dfn);//dfs序
ts = cnt = 0;//时间戳
for (int i = 1; i <= n; i ++ )
if (!dfn[i])//如果没被搜过就缩点
tarjan(i);
// 如果cnt==n ,没有环,把所有入边的权重求和即为答案
if (cnt == n)
{
for (int i = 2; i <= n; i ++ ) res += d[pre[i]][i];
break;
}
// 否则 先把环里的所有边权累加起来
for (int i = 2; i <= n; i ++ )
if (id[pre[i]] == id[i])//判断规则: 边的起点和终点是否在一个scc内
res += d[pre[i]][i];
// 初始化bd数组 作为G'的距离
for (int i = 1; i <= cnt; i ++ )
for (int j = 1; j <= cnt; j ++ )
bd[i][j] = INF;
// 构建新图G'
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
if (d[i][j] < INF && id[i] != id[j])//有边 且 是环外的边
{
int a = id[i], b = id[j];//起点a 终点b
// 如果终点在环内 则该入边 w' = w - w[环内入边权] = d[i][j] - d[pre[j][j]]
if (id[pre[j]] == id[j]) bd[a][b] = min(bd[a][b], d[i][j] - d[pre[j]][j]);
else bd[a][b] = min(bd[a][b], d[i][j]);
}
// n更新为新的点数 , d更新为bd
n = cnt;
memcpy(d, bd, sizeof d);
}
return res;
}
int main()
{
while (~scanf("%d%d", &n, &m))
{
for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);
memset(g, 0, sizeof g);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
if (a != b && b != 1) g[a][b] = true;
}
if (!check_con()) puts("poor snoopy");//不连通 无解
else printf("%.2lf\n", work());
}
return 0;
}