题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2121
Ice_cream’s world II
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5832 Accepted Submission(s): 1493
0 1 1
4 4
0 1 10
0 2 10
1 3 20
2 3 30
40 0
题解:
1.题目要求:给定一幅有向图,求最小树形图(根节点不确定)。
2.一开始想枚举每个结点作为根节点,然后跑zhuliu算法,求出最小值。结果发现复杂度太大。
3.可行做法:设置一个超级点,作为虚拟的根节点,把超级点连向每一个题目中的点。然后跑zhuliu算法,如果所得的最小树形图中只有一条超级边(超级点连向题目中的点,这个点就是实际的根节点),那么就求出实际了最小树形图;如果有多条超级边(实际得到的为最小树形图森林),则无解。
4.那么超级边的权值应该设为多少呢?由于我们需要从zhuliu算法返回的数据中判断出有多少条超级边,所以超级边就应该设置的足够大,以方便检测,但又不能溢出。所以我们将其设置为题目中所有边的权值之和+1。这样,只要zhuliu()返回来的数据:ans<2*super_edge,就表明只含有一条超级边,所以最终答案为ans-super_edge(减去人工设置的超级边)。否则,如果ans>=2*super_edge,则表明至少有两条超级边,也就说明了:在实际的图中(没有超级点),至少有两个结点是没有入边的。然而没有入边的结点只能有1个或者没有(作为根节点),所以无解。
代码如下:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = INT_MAX;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXN = 1e3+; struct Edge
{
int u, v, w;
}edge[]; //super_edge为超级点连向每个普通点的边权, root_pos用于记录实际的根节点。
int super_edge, root_pos;
int pre[MAXN], id[MAXN], vis[MAXN], in[MAXN]; int zhuliu(int root, int n, int m)
{
int res = ;
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].w<in[edge[i].v])
{
pre[edge[i].v] = edge[i].u;
in[edge[i].v] = edge[i].w;
//为什么可以这样记录实际的根节点呢?因为在main()函数中,我们设置超级点连向普通点的时候,
//边的下标从m开始,对应着结点0, m+1对应着结点1,………所以我们可以根据边的下标得出边的终点。
if(edge[i].u==root)
root_pos = i; } for(int i = ; i<n; i++)
if(i!=root && in[i]==INF)
return -; int tn = ;
memset(id, -, sizeof(id));
memset(vis, -, sizeof(vis));
in[root] = ;
for(int i = ; i<n; i++)
{
res += in[i];
int v = i;
while(vis[v]!=i && id[v]==- && v!=root)
{
vis[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 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].w -= in[v];
}
n = tn;
root = id[root];
}
return res;
} int main()
{
int n, m;
while(scanf("%d%d", &n, &m)!=EOF)
{
super_edge = ;
for(int i = ; i<m; i++)
{
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
super_edge += edge[i].w;
} super_edge++;
for(int i = ; i<n; i++) //n为超级点,将超级点连向每一个题目中的点
{
edge[m+i].u = n;
edge[m+i].v = i;
edge[m+i].w = super_edge;
} int ans = zhuliu(n, n+, m+n);
if(ans==- || ans>=*super_edge) printf("impossible\n\n");
else printf("%d %d\n\n", ans-super_edge, root_pos-m);
}
}