HDU2121

发表于 | 分类于 |

题目传送门

Description

一个女王的国家由$N$个城市和$M$条单向路组成，城市从$0$到$N-1$编号，每条路若要美化都有一个花费。现在女王要你选一个点为国都，并选择$N-1$条路进行美化，使其能从国都沿美化了的路到达每一个城市，且总花费最少。

Input

第一行：两个数字$N$、$M$ 。

接下来M行：每行三个数字$S$、$T$、$C$，分别表示这条路的起点编号、终点编号和美化花费。

Output

一行：两个数字，分别表示最小总花费和国都编号。

Solution

最小树形图，每个点选入边中边权最小的那个，缩点。

但是没有根怎么办？

自己建一个根，并在根与其他所有点之间连一条指向其他点的，费用为无限大的边。

新建的根可以保证算法的可行性，费用设为无限大可以保证最后有且只有一个点与根相连，这个点就是实际的国都。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include<cstdio>
#include<cstdlib>
#include<string.h>
#include<algorithm>
#include<queue>
#include<stack>
#define INF 0x3f3f3f3f
using namespace std;
const int maxn=1010;
const int maxm=10100;
int n,m,root,ans1,ans2;
bool asd;
struct EDGE
{
	int u,v,cost,num,pointto;
	EDGE *next,*fenext;
}edge[maxm+maxn],*ind[maxn],*feind[maxn];
int el=-1;
void input(int u,int v,int cost)
{
	edge[++el].u=u;
	edge[el].pointto=v;
	edge[el].num=el;
	edge[el].v=v;
	edge[el].cost=cost;
	edge[el].next=ind[u];
	ind[u]=&edge[el];
	edge[el].fenext=feind[v];
	feind[v]=&edge[el];
}
bool vis[maxn],scc[maxn];
int fa[maxn],mc[maxn],cedge[maxn];
bool MST()
{
	memset(vis,0,sizeof(vis));
	
	for(int i=0;i<=el;i++)
	{
		int u=edge[i].u,v=edge[i].v,c=edge[i].cost;
		if(!scc[u]&&!scc[v])
			if(mc[v]>=c)
			{
				fa[v]=u,mc[v]=c;cedge[v]=edge[i].num;
			}
	}
	int sumr=0;
	for(int i=n-1;i>=0;i--)
	{
		if(fa[i]==root)
		{
			if(sumr) return asd=0;
			else sumr++;
		}
		if(!scc[i]&&fa[i]==-1)
		{
			return asd=0;
		}
	}
	
	for(int i=n;i>=0;i--)
		if(!scc[i])
		{
			memset(vis,0,sizeof(vis));
			vis[root]=1;
			int v=i;
			for(;!vis[v];v=fa[v])
				vis[v]=true;
			if(v==root) continue;
			
			int u=v;
			do
			{
				scc[v]=1;
				v=fa[v];
			}while(u!=v);
			do
			{
				ans1+=mc[v];
				EDGE *k1;
				for(EDGE *k=ind[v];k!=NULL;k=k1)
				{
					k1=k->next;
					if(scc[k->v]||k->u==u) continue;
					k->u=u;
					k->next=ind[u];
					ind[u]=k;
				}
				for(EDGE *k=feind[v];k!=NULL;k=k1)
				{
					k1=k->fenext;
					if(scc[k->u]) continue;
					k->cost-=mc[v];
					if(k->v==u) continue;
					k->v=u;
					k->fenext=feind[u];
					feind[u]=k;
				}
				if(v!=u)
				{
					ind[v]=NULL;
					feind[v]=NULL;
				}
				mc[v]=0;
				v=fa[v];
			}while(u!=v);
			scc[u]=0;
			mc[u]=INF+1;
			fa[u]=-1;
			return 1;
		}
	for(int i=n-1;i>=0;i--)
		if(!scc[i]) ans1+=mc[i];
	return 0;
}
void init();
int main()
{
	while(scanf("%d%d",&n,&m)==2)
	{
		init();
		for(int i=n-1;i>=0;i--) input(root,i,INF);
		for(int i=1;i<=m;i++)
		{
			int x,y,c;
			scanf("%d%d%d",&x,&y,&c);
			input(x,y,c);
		}
		if(n==0) printf("-1 0\n\n");
		else if(n==1) printf("0 0\n\n");
		else
		{
			while(MST());
			if(asd)
				for(int i=0;i<n;i++)
					if(!scc[i]&&fa[i]==root)
						ans2=edge[cedge[i]].pointto;
			if(!asd) printf("impossible\n\n");
			else printf("%d %d\n\n",ans1-int(INF),ans2);
		}
	}
	return 0;
}
void init()
{
	root=n;
	asd=1;
	ans1=0;ans2=0;
	el=-1;
	for(int i=0;i<=n;i++) ind[i]=NULL,feind[i]=NULL,mc[i]=INF+1;
	memset(scc,0,sizeof(scc));
	memset(fa,n+1,sizeof(fa));
}