題意：
給定n個點 m條有向邊（點標從1開始）
下面n個點坐標
下面m條邊
問最小樹形圖權值（無則輸出一句話）
思路：最小樹形圖裸題
#include
#include
#include
#include
#include
using namespace std;
/*
* 最小樹形圖
* 復雜度O(NM)
* 點從0開始
*/
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 40010;
struct Edge{
int u,v;
double cost;
}edge[MAXM];
int pre[MAXN],id[MAXN],visit[MAXN];
double in[MAXN];
double zhuliu(int root,int n,int m,Edge edge[])
{
int u,v;
double res=0;
while(1)
{
for(int i = 0;i < n;i++)
in[i] = INF;
for(int i = 0;i < m;i++)
if(edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v])
{
pre[edge[i].v] = edge[i].u;
in[edge[i].v] = edge[i].cost;
}
for(int i = 0;i < n;i++)
if(i != root && in[i] == INF)
return -1;//不存在最小樹形圖
int tn = 0;
memset(id,-1,sizeof(id));
memset(visit,-1,sizeof(visit));
in[root] = 0;
for(int i = 0;i < n;i++)
{
res += in[i];
v = i;
while( visit[v] != i && id[v] == -1 && v != root)
{
visit[v] = i;
v = pre[v];
}
if( v != root && id[v] == -1 )
{
for(int u = pre[v]; u != v ;u = pre[u])
id[u] = tn;
id[v] = tn++;
}
}
if(tn == 0)break;//沒有有向環
for(int i = 0;i < n;i++)
if(id[i] == -1)
id[i] = tn++;
for(int i = 0;i < m;)
{
v = edge[i].v;
edge[i].u = id[edge[i].u];
edge[i].v = id[edge[i].v];
if(edge[i].u != edge[i].v)
edge[i++].cost -= in[v];
else
swap(edge[i],edge[--m]);
}
n = tn;
root = id[root];
}
return res;
}
double dis[105][105];
struct node{
double x,y;
}p[105];
double Dis(node a, node b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int n, m;
int main()
{
int i, j, u, v; double d;
while(~scanf("%d %d", &n, &m)){
for(i = 0; i < n; i++)
{
scanf("%lf%lf",&p[i].x,&p[i].y);
for(j = 0; j < n; j++)dis[i][j] = INF;
}
while(m--){
scanf("%d%d",&u,&v); u--, v--;
dis[u][v] = min(dis[u][v], Dis(p[u],p[v]));
}
int edgenum = 0;
for(i = 0; i < n; i++)if(i!=j)
for(j = 0; j < n; j++)if(dis[i][j]
