「bzoj2481」Command Network - 最小树形图

题目大意

    MST（最小生成树）：对于无向带权图，若其导出子图的边权和最小，且原图$V$中对应的任意两个顶点间有且仅有一条通路，则称此图为原图的MST。
    你的任务很简单，对于给定的有向带权图，求出其“最小生成树”，即指定一个根以后，每个点都是从根出发可达的。

---

题目分析

本题和$pku3164$有很大不同。
请不要将$pku3164$当作朱刘算法模板题。

朱刘算法就是结合缩点的贪心算法。
每一次贪心选取入边权值最小的边累加进入答案。
如果选取的边构成了环就缩环，并将指向环的所有入边的权值减去被指向点原来的最小入边的权值（以防重复统计），缩环后继续执行贪心算法。

本题没有指定源点，需要新建虚点。
判断无解可以根据连通块的数目进行判断。

因为朱刘算法是$O(nm)$的，时间复杂度略高，若想优化时间可以采用（xyj发明的）玄学方法：若边数量大于一定阈值，将边集按照权值从小到大排序，仅保留前面的$\frac14$条边。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
 
inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}
 
const int maxn=1005;
 
struct Edge {
	int from,to,dist;
	Edge(int x=0,int y=0,int v=0):from(x),to(y),dist(v) {}
};
 
int Directed_MST(int n,vector<Edge>edges,int root) {
	double ans=0;
	static int in[maxn];
	static int id[maxn],pre[maxn],vst[maxn];
	while(true) {
		//找最小入边
		for(int i=1; i<=n; i++)in[i]=INT_MAX;
		for(Edge& e:edges) {
			int x=e.from,y=e.to;
			if(x==y)continue;
			if(e.dist<in[y]) {
				pre[y]=x;
				in[y]=e.dist;
			}
		}
		//找环
		memset(id,0,sizeof(id));
		memset(vst,0,sizeof(vst));
		int cnt=0;
		in[root]=0;
		for(int i=1; i<=n; i++) {
			ans+=in[i];
			int now;
			for(now=i; vst[now]!=i&&!id[now]&&now!=root; now=pre[now])vst[now]=i; //找环
			if(now!=root&&!id[now]) { //缩点
				id[now]=++cnt;
				for(int p=pre[now]; p!=now; p=pre[p])id[p]=cnt;
			}
		}
		if(cnt==0)break; //无环
		for(int i=1; i<=n; i++)
			if(!id[i])id[i]=++cnt;
		for(Edge& e:edges) {
			int &x=e.from,&y=e.to;
			if(x!=y)e.dist-=in[y];
			x=id[x];
			y=id[y];
		}
		n=cnt;
		root=id[root];
	}
	return ans;
}
 
int n,m,InDegree[maxn];
vector<Edge>edges;
 
struct Point {
	int x,y;
} p[maxn];
 
int Dist(Point a,Point b) {
	return abs(a.x-b.x)+abs(a.y-b.y);
}
 
int main() {
	while(~scanf("%d%d",&n,&m)) {
		edges.clear();
		memset(InDegree,0,sizeof(InDegree)); 
		for(int i=1; i<=n; i++)scanf("%d%d",&p[i].x,&p[i].y);
		for(int i=1; i<=m; i++) {
			int x=Get_Int(),y=Get_Int();
			if(x!=y) {
				edges.push_back(Edge(x,y,Dist(p[x],p[y])));
				InDegree[y]++;
			} 
		}
		int cnt=0;
		for(int i=1; i<=n; i++)
			if(!InDegree[i])cnt++;
		if(cnt>1) {
			puts("Poor");
			continue;
		}
		int root=n+1;
		for(int i=1; i<=n; i++)edges.push_back(Edge(root,i,100000));
		int ans=Directed_MST(n+1,edges,root);
		printf("%d\n",ans-100000);
	}
	return 0;
}