日常%一发mmh学长。
时间复杂度为O（n * m）。
据说tarjan大神有一个（m+nlogn）的算法，但是找不到资料。。。
①P4716 【模板】最小树形图：
题目背景
这是一道模板题。
题目描述
给定包含 n 个结点， m 条有向边的一个图。试求一棵以结点 r 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 r 为根的最小树形图，输出 −1。
输入格式
第一行包含三个整数 n,m,r，意义同题目所述。
接下来 m 行，每行包含三个整数 u,v,w，表示图中存在一条从 u 指向 v 的权值为 w 的有向边。
输出格式
如果原图中存在以 r 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 −1。
输入输出样例
输入 #1 复制
4 6 1
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1
输出 #1 复制
3
输入 #2 复制
4 6 3
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1
输出 #2 复制
4
输入 #3 复制
4 6 2
1 2 3
1 3 1
4 1 2
4 2 2
3 2 1
3 4 1
输出 #3 复制
-1
说明/提示
样例 1 解释
最小树形图中包含第 2， 5， 6 三条边，总权值为 1 + 1 + 1 = 3
样例 2 解释
最小树形图中包含第 3， 5， 6 三条边，总权值为 2 + 1 + 1 = 4
样例 3 解释
无法构成最小树形图，故输出 −1 。
数据范围
对于所有数据，1≤u,v≤n≤100, 1≤m≤1e4
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=110;
const int inf=0x3f3f3f3f;
int n,m,root;
int in[maxn],id[maxn],pre[maxn],ha[maxn];
struct node
{
int x,y,z;
}a[maxn*maxn];
int zl(void)
{
int ans=0;
while(1)
{
int cnt=0;
//初始化
for(int i=1;i<=n;i++)
in[i]=inf,ha[i]=0,id[i]=0;
//求最小入边
for(int i=1;i<=m;i++)
{
if(a[i].x==a[i].y) continue;
if(in[a[i].y]>a[i].z)
{
in[a[i].y]=a[i].z;
pre[a[i].y]=a[i].x;
}
}
//有除了根节点以外的孤立点
//则不存在
for(int i=1;i<=n;i++)
if(i!=root&&in[i]==inf) return -1;
for(int i=1;i<=n;i++)
{
if(i==root) continue;
ans+=in[i];
int t=i;
while(ha[t]!=i&&!id[t]&&t!=root)
ha[t]=i,t=pre[t];
if(!id[t]&&t!=root)
{
id[t]=++cnt;
for(int j=pre[t];j!=t;j=pre[j])
id[j]=cnt;
}
}
//无环则成功找到最小生成树
if(!cnt) break;
for(int i=1;i<=n;i++)
if(!id[i]) id[i]=++cnt;
for(int i=1;i<=m;i++)
{
int y=a[i].y;
a[i].x=id[a[i].x];
a[i].y=id[a[i].y];
if(a[i].x!=a[i].y) a[i].z-=in[y];
}
n=cnt;
root=id[root];
}
return ans;
}
int main(void)
{
scanf("%d%d%d",&n,&m,&root);
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
printf("%d\n",zl());
return 0;
}
②、Command Network POJ - 3164：
After a long lasting war on words, a war on arms finally breaks out between littleken’s and KnuthOcean’s kingdoms. A sudden and violent assault by KnuthOcean’s force has rendered a total failure of littleken’s command network. A provisional network must be built immediately. littleken orders snoopy to take charge of the project.
With the situation studied to every detail, snoopy believes that the most urgent point is to enable littenken’s commands to reach every disconnected node in the destroyed network and decides on a plan to build a unidirectional communication network. The nodes are distributed on a plane. If littleken’s commands are to be able to be delivered directly from a node A to another node B, a wire will have to be built along the straight line segment connecting the two nodes. Since it’s in wartime, not between all pairs of nodes can wires be built. snoopy wants the plan to require the shortest total length of wires so that the construction can be done very soon.
Input
The input contains several test cases. Each test case starts with a line containing two integer N (N ≤ 100), the number of nodes in the destroyed network, and M (M ≤ 104), the number of pairs of nodes between which a wire can be built. The next N lines each contain an ordered pair xi and yi, giving the Cartesian coordinates of the nodes. Then follow M lines each containing two integers i and j between 1 and N (inclusive) meaning a wire can be built between node i and node j for unidirectional command delivery from the former to the latter. littleken’s headquarter is always located at node 1. Process to end of file.
Output
For each test case, output exactly one line containing the shortest total length of wires to two digits past the decimal point. In the cases that such a network does not exist, just output ‘poor snoopy’.
Sample Input
4 6
0 6
4 6
0 0
7 20
1 2
1 3
2 3
3 4
3 1
3 2
4 3
0 0
1 0
0 1
1 2
1 3
4 1
2 3
Sample Output
31.19
poor snoopy
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=110;
const int inf=0x3f3f3f3f;
int n,m,root;
int id[maxn],pre[maxn],ha[maxn];
double in[maxn];
struct Node
{
double x,y;
}b[maxn];
struct node
{
int x,y;
double z;
node(){}
node(int a,int b,double c)
{
x=a,y=b,z=c;
}
}a[maxn*maxn];
double dis(int p,int q)
{
return hypot(b[p].x-b[q].x,b[p].y-b[q].y);
}
double zl(void)
{
double ans=0;
while(1)
{
int cnt=0;
//初始化
for(int i=1;i<=n;i++)
in[i]=inf,ha[i]=0,id[i]=0;
//求最小入边
for(int i=1;i<=m;i++)
{
if(a[i].x==a[i].y) continue;
if(in[a[i].y]>a[i].z)
{
in[a[i].y]=a[i].z;
pre[a[i].y]=a[i].x;
}
}
//有除了根节点以外的孤立点
//则不存在
for(int i=1;i<=n;i++)
if(i!=root&&in[i]==inf) return -1;
for(int i=1;i<=n;i++)
{
if(i==root) continue;
ans+=in[i];
int t=i;
while(ha[t]!=i&&!id[t]&&t!=root)
ha[t]=i,t=pre[t];
if(!id[t]&&t!=root)
{
id[t]=++cnt;
for(int j=pre[t];j!=t;j=pre[j])
id[j]=cnt;
}
}
//无环则成功找到最小生成树
if(!cnt) break;
for(int i=1;i<=n;i++)
if(!id[i]) id[i]=++cnt;
for(int i=1;i<=m;i++)
{
int y=a[i].y;
a[i].x=id[a[i].x];
a[i].y=id[a[i].y];
if(a[i].x!=a[i].y) a[i].z-=in[y];
}
n=cnt;
root=id[root];
}
return ans;
}
int main(void)
{
while(scanf("%d%d",&n,&m)!=EOF)
{
root=1;
for(int i=1;i<=n;i++)
scanf("%lf%lf",&b[i].x,&b[i].y);
int x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
a[i]=node(x,y,dis(x,y));
}
double ans=zl();
if(ans==-1) printf("poor snoopy\n");
else printf("%.2f\n",ans);
}
return 0;
}
③、Ice_cream’s world II HDU - 2121：
不定根最小树形图：
无根最小树形图，构造根节点0，从0到各点建立权值大于整张图权值和的边（此处取sum+1），这样一来0为根节点求最小树形图，如果不存在最小树形图或者所得最小树形图的权值和不小于2*(sum+1)说明原图的最小树形图不存在，至于如何求编号最小的根节点，这个可以在求最短弧集合的时候得到，即如果一条边被加入最短弧集合且这条边的起点是0，那么这条边的终点就是所求最小树形图的根。
对于本题，节点编号为0–n，那么我们就用节点n作为超级源点。
After awarded lands to ACMers, the queen want to choose a city be her capital. This is an important event in ice_cream world, and it also a very difficult problem, because the world have N cities and M roads, every road was directed. Wiskey is a chief engineer in ice_cream world. The queen asked Wiskey must find a suitable location to establish the capital, beautify the roads which let capital can visit each city and the project’s cost as less as better. If Wiskey can’t fulfill the queen’s require, he will be punishing.
Input
Every case have two integers N and M (N<=1000, M<=10000), the cities numbered 0…N-1, following M lines, each line contain three integers S, T and C, meaning from S to T have a road will cost C.
Output
If no location satisfy the queen’s require, you must be output “impossible”, otherwise, print the minimum cost in this project and suitable city’s number. May be exist many suitable cities, choose the minimum number city. After every case print one blank.
Sample Input
3 1
0 1 1
4 4
0 1 10
0 2 10
1 3 20
2 3 30
Sample Output
impossible
40 0
代码未验证，HDU好像崩了。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<vector>
#define ll long long
#define llu unsigned ll
using namespace std;
const int maxn=1010;
const int inf=0x3f3f3f3f;
int n,m,pos;
int id[maxn],pre[maxn],ha[maxn],in[maxn];
struct node
{
int x,y,z;
node(){}
node(int a,int b,int c)
{
x=a,y=b,z=c;
}
}a[maxn*11];
int zl(int root,int n,int m)
{
int ans=0;
while(1)
{
int cnt=0;
//初始化
for(int i=0;i<n;i++)
in[i]=inf,ha[i]=-1,id[i]=-1;
//求最小入边
for(int i=0;i<m;i++)
{
if(a[i].x==a[i].y) continue;
if(in[a[i].y]>a[i].z)
{
in[a[i].y]=a[i].z;
pre[a[i].y]=a[i].x;
if(a[i].x==root) pos=i;
}
}
//有除了根节点以外的孤立点
//则不存在
for(int i=0;i<n;i++)
if(i!=root&&in[i]==inf) return -1;
for(int i=0;i<n;i++)
{
if(i==root) continue;
ans+=in[i];
int t=i;
while(ha[t]!=i&&id[t]==-1&&t!=root)
ha[t]=i,t=pre[t];
if(id[t]==-1&&t!=root)
{
id[t]=cnt;
for(int j=pre[t];j!=t;j=pre[j])
id[j]=cnt;
cnt++;
}
}
//无环则成功找到最小生成树
if(!cnt) break;
for(int i=0;i<n;i++)
if(id[i]==-1) id[i]=cnt++;
for(int i=0;i<m;i++)
{
int y=a[i].y;
a[i].x=id[a[i].x];
a[i].y=id[a[i].y];
if(a[i].x!=a[i].y) a[i].z-=in[y];
}
n=cnt;
root=id[root];
}
return ans;
}
int main(void)
{
while(scanf("%d%d",&n,&m)!=EOF)
{
int ans=0;
for(int i=0;i<m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
ans+=a[i].z;
}
ans++;
for(int i=0;i<n;i++)
{
a[i+m].x=n;
a[i+m].y=i;
a[i+m].z=ans;
}
int res=zl(n,n+1,n+m);
if(res==-1||res>=2*ans) printf("impossible\n");
else printf("%d %d\n",res-ans,pos-m);
putchar('\n');
}
return 0;
}
京公网安备 11010502036488号