Ice_cream’s world II
题意:给定一个有向图,求最小生成树是否存在,若存在则求出根节点以及最小权值。
思路:利用朱刘算法,推荐博客
- 求最短弧集合E0
- 检查E0
- 收缩G中的有向环
- 展开收缩点
(以下代码节点下标从 0开始)
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<ll,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 1e3+10;
const int mod = 1e9+7;
const double eps = 1e-7;
const int INF = 2e9;
struct Edge{
int u, v;
ll w;
}edge[maxn*maxn];
int pre[maxn], id[maxn], vis[maxn], n, m, pos;
ll in[maxn];//存最小入边权,pre[v]为该边的起点
ll Directed_MST(int root, int V, int E) {
ll ret=0;//存最小树形图总权值
while(1) {
//1.找每个节点的最小入边
for(int i=0; i<V; ++i) in[i]=INF;//初始化为无穷大
for(int i=0; i<E; ++i) {//遍历每条边
int u=edge[i].u;
int v=edge[i].v;
if(edge[i].w<in[v]&&u!=v) {
pre[v]=u;
in[v]=edge[i].w;
if(u==root) pos=i;
}
}
for(int i=0; i<V; ++i) {//判断是否存在最小树形图
if(i==root) continue;
if(in[i]==INF) return -1;
}
//2.找环
int cnt=0; //记录环数
memset(id,-1,sizeof(id));
memset(vis,-1,sizeof(vis));
in[root]=0;
for(int i=0; i<V; ++i) {//标记每个环
ret+=in[i];//记录权值
int v=i;
while(vis[v]!=i&&id[v]==-1&&v!=root) {
vis[v]=i;
v=pre[v];
}
if(v!=root&&id[v]==-1) {
for(int u=pre[v]; u!=v; u=pre[u]) id[u]=cnt;
id[v]=cnt++;
}
}
if(cnt==0) break; //无环
for(int i=0; i<V; ++i) if(id[i]==-1) id[i]=cnt++;
//3.建立新图 缩点,重新标记
for(int i=0; i<E; ++i) {
int u=edge[i].u;
int v=edge[i].v;
edge[i].u=id[u];
edge[i].v=id[v];
if(id[u]!=id[v]) edge[i].w-=in[v];//减去in[v]的原因是若选择这条边,则不需要选择已经选择过的v的那条最小入边,因此要把那条入边减去
}
V=cnt, root=id[root];
}
return ret;
}
int main() {
//ios::sync_with_stdio(false);
while(scanf("%d%d", &n, &m)!=EOF) {
ll sum=0;
for(int i=0; i<m; ++i) {
scanf("%d%d%lld", &edge[i].u, &edge[i].v, &edge[i].w);
sum+=edge[i].w;
}
sum++;
for(int i=m; i<m+n; ++i) {//增加超级节点n,节点n到其余个个节点的边权相同(此题中,边权要大于原图的总边权)
edge[i].u=n;
edge[i].v=i-m+1;
edge[i].w=sum;
}
ll ans=Directed_MST(n,n+1,m+n);
//n+1为总结点数,m+n为总边数
//ans代表以超级节点0为根的最小树形图的总权值
//将ans减去sum,如果差值小于sum,说明节点0的出度只有1,即原图是连通图
//如果差值>=sum,那么说明节点0的出度不止为1,即原图不是连通图
if(ans==-1||ans-sum>=sum) printf("impossible\n");
else printf("%lld %d\n", ans-sum, pos-m);
puts("");
}
}