Untitled

Go Back — Change Paste Viewing Options

Виталий Павленко
ЮграНефтеТранс(Частичное решение)
115
#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <vector>
 
using namespace std;
 
const int maxn = 2010;
const int maxm = 100100;
const double T0 = 100;
const int maxk = 50;
 
double alpha = 0.99;
 
struct solution {
	bool a[maxn];
	int cost;
};
 
int n, m, k, t = 0;
double T = T0;
pair<int, int> edges[maxm];
vector< vector <int> > adj(maxn, vector<int> ());
solution curr, next, best;
int a[maxk];
bool b[maxn];
 
void check() {
	bool flag = true;
	for (int i = 0; i < m; ++i)
		flag = flag && (b[edges[i].first] || b[edges[i].second]);
	if (flag) {
		printf("Yes\n");
		for (int i = 1; i <= k; ++i) 
			printf("%d ", a[i] + 1);
		exit(0);
	}	
}
 
void rec(int level) {
	for (int i = a[level - 1] + 1; i < n; ++i) {
		a[level] = i;
		b[i] = true;
		if (level < k) {
			rec(level + 1);
		} else {
			check();
		}
		b[i] = false;
	}
}
 
void alternate() {
	a[0] = -1;
	for(int i = 0; i < n; ++i)
		b[i] = false;
	rec(1);
}
 
void setcost(solution& sol) {
	sol.cost = m;
	for(int i = 0; i < m; ++i) {
		if (sol.a[edges[i].first] || sol.a[edges[i].second])
			sol.cost--;
	}
}
 
int calcbadedges(int vertex, solution& sol) {
	int res = 0;
	for(int i = 0; i < int(adj[vertex].size()); i++) {
		if (!(sol.a[edges[adj[vertex][i]].first] || sol.a[edges[adj[vertex][i]].second]))
			res++;
	}
	return res;
}
 
void setnext(solution& sol) {
	int before, after;
	for(int cnt = 0; cnt <= T; ++cnt) {
		int a = rand() % n, b = rand() % n;
		before = calcbadedges(a, sol) + calcbadedges(b, sol);
		swap(sol.a[a], sol.a[b]); 
		after = calcbadedges(a, sol) + calcbadedges(b, sol);
		sol.cost -= before - after;
	}
//	setcost(sol);
}
 
bool admit(int dF) {
	return dF < 0 || exp(-dF / T) > rand() / double(RAND_MAX);
}
 
int main() {
	clock_t start = clock();
	srand(3271);
 
//	freopen("pipeline.in", "r", stdin);
//	freopen("pipeline.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	for(int i = 0; i < m; ++i) {
		scanf("%d%d", &edges[i].first, &edges[i].second);
		edges[i].first--;
		edges[i].second--;
		adj[edges[i].first].push_back(i);
		adj[edges[i].second].push_back(i);
	}
	if (m * pow(double(n), k) < 10000000) {
		cerr << "brute force\n";
		alternate();
		printf("No\n");
		return 0;
	}
	cerr << "annealing\n";
	T = n;
	alpha = pow(1 / T, m / 1200000.0);
//	printf("alpha: %f\n", alpha);
	for(int i = 0; i < k; ++i) {
		curr.a[i] = true;
	}
	for(int i = k; i < n; ++i) {
		curr.a[i] = false;
	}
	setcost(curr);
	best = curr;
	int t = 0;
 
	while(best.cost > 0) {
		t++;
		next = curr;
		setnext(next);
		if (admit(next.cost - curr.cost)) {
			curr = next;
			if (curr.cost < best.cost)
				best = curr;
		}
		if (t > (1000000.0 / m) / 1000) {
			if ((clock() - start) / double(CLOCKS_PER_SEC) > 1.95) {
				printf("No\n");
//				printf("t = %d, T = %f\n", t, T);
				return 0;
			}
		}
		t++;
		T *= alpha;
	}
	//printf("t = %d, T = %f\n", t, T);
	printf("Yes\n");
	for(int i = 0; i < n; ++i)
		if (best.a[i]) 
			printf("%d ", i + 1);
	scanf("\n");
	return 0;
}			

Go Back