给你一张 nn 个点mm 条边的无向图（点从00到n−1n-1标号），走过每条边都需要花费 11 秒

给你一个整数 kk ，请你选择至多 kk 个点，令经过这些点也需要花费 11 秒，使得从点 00 走到点 n−1n-1 的最短时间最大，求这个最大值

注意，不能选择点 00 或点

n≤100,m≤n(n−1)2n\le100, m\le\frac{n(n-1)}{2}

FZOJ 190

Brute-Force

看到数据范围这么小，可以考虑模拟退火乱搞。

先随机选kk个点，每次随机交换两个点，看答案是否更优

注意到，这里的退火并不是真正意义上的退火。因为每次变动解的范围是和TT无关的，也就相当于是一个乱搞做法，不过能获得9898分的高分。。。

Solution

考虑一个显然对的贪心

每次找到一个大小尽量小的点集SS，使得从00到n−1n-1的任意一条最短路中都存在某个点x∈Sx\in S。然后把SS的点权设为11，再计算一遍最短路，重复以上过程

考虑如何求点集SS

不难注意到，SS实际上就是原图的最短路图的最小割点集（即在最短路图中，删掉这个集合就能使得00和n−1n-1不联通）

于是就很容易转化成一个网络流模型了

  • 把 到 的每个点 拆成两个点 。从 向 连边，若 点权已经为 ，则容量为 ；否则为
  • 把原图最短路图中的边对应连到此处从左列点往右列点的边，容量为∞\infty。最短路图中与00或n−1n-1相连的边直接从源点连向第二列的点，或是从第一列的点连向汇点

这样做就能将割点集转化成割边集，直接求最小割即可

Code

Brute-Force

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
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 110, Maxm = Maxn * Maxn;

inline int Rand(int l, int r) { if (r - l + 1 <= 0) return -1; return rand() % (r - l + 1) + l; }

int N, M, K;
int e, To[Maxm], Begin[Maxn], Next[Maxm];
int Val[Maxn], A[Maxn], n, m, k, Vis[Maxn], Dis[Maxn];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

priority_queue<pii , vector<pii> , greater<pii> > Q;

inline int Dijsktra ()
{
	Q.push (mp(0, 0));
	memset (Dis, 0x3f, sizeof(Dis)), Dis[0] = 0;
	memset (Vis, 0, sizeof(Vis));

	while (!Q.empty())
	{
		int x = Q.top().y; Q.pop();
		if(Vis[x]) continue;
		Vis[x] = 1;

		for(int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (Chkmin(Dis[y], Dis[x] + Val[x] + 1)) Q.push(mp(Dis[y], y));
		}
	}

	return Dis[N - 1];
}

int now_ans, ans;

inline void Init() { random_shuffle(A + 1, A + N - 1); for (int i = 1; i <= K; ++i) Val[A[i]] = 1; }

const double TIME_LIMIT = 0.9;
const double delta = 0.98;
const double eps = 1e-8;

inline void Work ()
{
	now_ans = Dijsktra(); Chkmax(ans, now_ans);
	double temp = 10000000;
	while (temp > eps)
	{
		int x = Rand(1, K), y = Rand(K + 1, N - 2);

		if (x != -1 && y != -1)
		{
			swap(A[x], A[y]); swap(Val[A[x]], Val[A[y]]); 

			int now = Dijsktra(); 
			Chkmax(ans, now);

			if(now > now_ans || exp((now - now_ans) / temp) * RAND_MAX > rand())
				now_ans = now;
			else swap(A[x], A[y]), swap(Val[A[x]], Val[A[y]]);
		}

		temp *= delta;

		if (clock() / CLOCKS_PER_SEC > TIME_LIMIT)
		{
			cout << ans << endl;
			exit(0);
		}
	}

	for(int i = 0; i < N; ++i) Val[i] = 0;
}

inline void Solve ()
{
	for(int i = 1; i < N - 1; ++i) A[i] = i;

	while(clock() / CLOCKS_PER_SEC < TIME_LIMIT) Init (), Work ();

	cout << ans << endl;
}

inline void Input ()
{
	srand(20030216);
	N = read<int>(), M = read<int>();
	K = min(N - 2, read<int>());

	for(int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>();
		add_edge (x, y);
		add_edge (y, x);
	}
}

int main()
{

	freopen("min.in", "r", stdin);
	freopen("min.out", "w", stdout);

	Input();
	Solve();

	return 0;
}

std

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
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
#include <bits/stdc++.h>

#define x first
#define y second
#define y1 Y1
#define y2 Y2
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
	T sum = 0, fl = 1; char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
	for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

inline void proc_status ()
{
	ifstream t ("/proc/self/status");
	cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int Maxn = 100 + 20, Maxm = Maxn * Maxn + 100, inf = 0x3f3f3f3f;

int N, M, K;
int e, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1], W[Maxn];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

namespace Dinic
{
	const int Maxn = 200 + 20;
	int e = 1, Begin[Maxn], To[Maxm << 1], Next[Maxm << 1], Cur[Maxn];
	int Cap[Maxm << 1], Level[Maxn];

	inline void add_edge (int x, int y, int z, int p = 0)
	{
		To[++e] = y; Next[e] = Begin[x]; Begin[x] = e;
		Cap[e] = z; if (!p) add_edge (y, x, 0, 1);
	}

	queue <int> Q;

	inline int bfs ()
	{
		memset(Level, -1, sizeof Level);
		Level[1] = 0; Q.push(1);

		while (!Q.empty())
		{
			int x = Q.front(); Q.pop();
			for (int i = Begin[x]; i; i = Next[i])
			{
				int y = To[i];
				if (Cap[i] > 0 && Level[y] < 0)
				{
					Level[y] = Level[x] + 1;
					Q.push(y);
				}
			}
		}

		return Level[N] != -1;
	}

	inline int find (int x, int k)
	{
		if (x == N) return k;

		int ans = 0;
		for (int &i = Cur[x]; i; i = Next[i])
		{
			int y = To[i], sum;
			if (Level[y] == Level[x] + 1 && Cap[i] > 0 && (sum = find(y, min(Cap[i], k))))
			{
				k -= sum, Cap[i] -= sum;
				ans += sum, Cap[i ^ 1] += sum;
				if (!k) break;
			}
		}

		return ans;
	}

	inline int work ()
	{
		int ans = 0;
		while (bfs())
		{
			for (int i = 1; i <= 2 * N; ++i) Cur[i] = Begin[i];
			ans += find(1, inf);
		}

		for (int i = 2; i < N; ++i) if (Level[i + N] > 0 && Level[i] < 0) W[i] = 1;

		return ans;
	}
	
	inline void init ()
	{
		e = 1; memset(Begin, 0, sizeof Begin);
	}
}

int Vis[Maxn], Dis[Maxn];
queue <int> Q;
vector <int> From[Maxn];

inline int Spfa ()
{
	for (int i = 1; i <= N; ++i) Dis[i] = inf; 
	Dis[1] = 0, Q.push(1);

	while (!Q.empty())
	{
		int x = Q.front(); Q.pop();
		Vis[x] = 0;
		for (int i = Begin[x]; i; i = Next[i])
		{
			int y = To[i];
			if (Chkmin (Dis[y], Dis[x] + W[y] + 1))
			{
				if (!Vis[y]) Vis[y] = 1, Q.push(y);
				From[y].clear(), From[y].pb(x);
			}
			else if (Dis[y] == Dis[x] + W[y] + 1) From[y].pb(x);
		}
	}

	return Dis[N];
}

inline void Build_Graph ()
{
	Spfa(); Dinic :: init ();

	for (int x = 2; x < N; ++x)
	{
		Dinic :: add_edge (x + N, x, W[x] ? inf : 1);

		for (int y : From[x]) Dinic :: add_edge (y, x + N, inf);
	}

	for (int x : From[N]) Dinic :: add_edge (x, N, inf);
}

inline void Solve ()
{
	int ans = Spfa ();

	while (K)
	{
		Build_Graph ();
		int now = Dinic :: work ();
		if (!now || now > K) break;
		++ans, K -= now;
	}

	cout << ans << endl;
}

inline void Input ()
{
	N = read<int>(), M = read<int>(), K = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>() + 1, y = read<int>() + 1;
		add_edge (x, y);
		add_edge (y, x);
	}
}

int main()
{

	freopen("min.in", "r", stdin);
	freopen("min.out", "w", stdout);

	Input ();
	Solve ();

	return 0;
}