有向图最小生成树

有向图最小生成树

解析: 裸的有向图最小生成树

代码

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<utility>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<cmath>
#include<iterator>
#include<stack>
using namespace std;
const int INF=1e9+;
const int eps=0.0000001;
const int maxn=;
struct edge
{
int u,v,w;
edge(int u=,int v=,int w=):u(u),v(v),w(w){}
}E[];
int pre[maxn],InEdge[maxn],vis[maxn],id[maxn];
int Dir_MST(int root,int Vcnt,int Ecnt)
{
int ret=;
while(true)
{
for(int i=;i<=Vcnt;i++) InEdge[i]=INF;
for(int i=;i<=Ecnt;i++)
{
edge& e=E[i];
int u=e.u,v=e.v,w=e.w;
if(u==v) continue;
if(w<InEdge[v]) { InEdge[v]=w; pre[v]=u; } //找最小的指向v的边
}
InEdge[root]=;
for(int i=;i<=Vcnt;i++) if(i!=root&&InEdge[i]==INF) return -;//存在某个点跟整个图分离
int ID=;
for(int i=;i<=Vcnt;i++) vis[i]=id[i]=-;
for(int i=;i<=Vcnt;i++)
{
ret+=InEdge[i]; //把那些边加进答案
int a=i;
while(vis[a]!=i&&id[a]==-&&a!=root){ vis[a]=i; a=pre[a]; }
if(id[a]==-&&a!=root)
{
++ID;
for(int b=pre[a];b!=a;b=pre[b]) id[b]=ID; //重新编号
id[a]=ID;
}
}
if(ID==) return ret; //找到解
for(int i=;i<=Vcnt;i++) if(id[i]==-) id[i]=++ID; //独立的点编号
for(int i=;i<=Ecnt;i++)
{
edge& e=E[i];
int u=e.u,v=e.v;
e.u=id[u];
e.v=id[v];
if(id[u]!=id[v]) e.w-=InEdge[v]; //之前加的那一部分要减掉
}
Vcnt=ID;
root=id[root];
}
}
int main()
{
int T,Case=;
scanf("%d",&T);
while(T--)
{
int N,M,u,v,w;
scanf("%d%d",&N,&M);
for(int i=;i<=M;i++)
{
scanf("%d%d%d",&u,&v,&w);
u++; v++;
E[i]=edge(u,v,w);
}
int ans=Dir_MST(,N,M);
printf("Case #%d: ",++Case);
if(ans==-) printf("Possums!\n");
else printf("%d\n",ans);
}
return ;
}
05-08 15:30