/*

最小树形图的第二题,终于有了一些理解

具体看注释

*/

/*
无定根的最小树形图
建立虚root
每次只找最短的那条入边
最小树形图理解:
第一步:寻找最短弧集E:扫一遍所有的边,找到每个点权值最小的入边,这一步会产生环
第二步:对每个点 i 找环:通过第一步记录的前驱找环,如果找到了原点或退到了另一个环,点i找环失败
第三步:缩点,缩点就是染色,把每个环内的点染上同一种颜色,每个环内点打上同一个id
第四步:更新一次边集:如果一条边连接两个不同颜色的点,就该边这条边的权值
重复以上四步。 最小树形图的root:root不需要入边
最小树形图的实质是最小生成树,所以用贪心的思想解决,但是贪心找入边时会生产环(第一步)
因此还得找另外一条边连到那个环中,才能解决这个环(第四步) 不定根确定根需要加一个虚根,由虚根为超级源点建立最小生成树,
这样由超级源点出发到达的第一个点就是实际最小生成树的根
虚根和每条边链接一条虚边,其权值要大于实根的和,以此判断是否连了两条虚边(建图失败) 如何找到那个实根:在不断形成环的过程中,会最先有一个点最先和虚根相连,这个点就是实根(实根是不需要入边的,但是在加了虚根后,实根不再是根)
贪心思想保证第一个和虚根链接的必定是实根
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll long long
#define MAXN 1005
#define INF 0x3f3f3f
using namespace std;
struct Edge{
ll u,v,cost;
}edge[MAXN*MAXN];
ll pos;
int pre[MAXN],id[MAXN],visit[MAXN];
ll in[MAXN];
ll zhuliu(int root,int n,int m){
int res=;
int u,v;
while(){
for(int i=;i<n;i++)
in[i]=INF;
for(int i=;i<m;i++)
if(edge[i].u!=edge[i].v && edge[i].cost<in[edge[i].v]){
in[edge[i].v]=edge[i].cost;
pre[edge[i].v]=edge[i].u;
if(edge[i].u==root)
pos=i;
}
for(int i=;i<n;i++)
if(i!=root && in[i]==INF)
return -; int tn=;
memset(id,-,sizeof id);
memset(visit,-,sizeof visit);
in[root]=;
for(int i=;i<n;i++){
res+=in[i];
v=i;
while(visit[v]!=i && id[v]==- && v!=root){
visit[v]=i;
v=pre[v];
}
if(v!=root && id[v]==-){
for(int u=pre[v];u!=v;u=pre[u])
id[u]=tn;
id[v]=tn++;
}
} if(tn==)
break;//已经没有环了
for(int i=;i<n;i++)
if(id[i]==-)
id[i]=tn++; for(int i=;i<m;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].cost-=in[v];
}
n=tn;
root=id[root];
}
return res;
}
int main(){
ll n,m;
while(scanf("%lld%lld",&n,&m)==){
ll sum=;
for(ll i=;i<m;i++){ scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].cost);
edge[i].u++;edge[i].v++;
sum+=edge[i].cost;
} int root=n,tot=m;//加入虚根
for(ll i=m;i<n+m;i++){
edge[i].u=;
edge[i].v=i-m+;
edge[i].cost=sum+;
} ll ans=zhuliu(,n+,n+m);
if(ans==- || ans-(sum+)>=sum+)
printf("impossible\n\n");
else
printf("%lld %lld\n\n",ans-(sum+),pos-m);
}
return ;
}
05-11 10:49