HDU3663-Power Stations

Power Stations

                                                                   Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
                                                                                           Total Submission(s): 2344    Accepted Submission(s): 698
                                                                                                                           Special Judge

Problem Description

There are N towns in our country, and some of them are connected by electricity cables. It is known that every town owns a power station. When a town’s power station begins to work, it will provide electric power for this town and the neighboring towns which are connected by cables directly to this town. However, there are some strange bugs in the electric system –One town can only receive electric power from no more than one power station, otherwise the cables will be burned out for overload.

The power stations cannot work all the time. For each station there is an available time range. For example, the power station located on Town 1 may be available from the third day to the fifth day, while the power station on Town 2 may be available from the first day to the forth day. You can choose a sub-range of the available range as the working time for each station. Note that you can only choose one sub-range for each available range, that is, once the station stops working, you cannot restart it again. Of course, it is possible not to use any of them.

Now you are given all the information about the cable connection between the towns, and all the power stations’ available time. You need to find out a schedule that every town will get the electricity supply for next D days, one and only one supplier for one town at any time.

 

Input

There are several test cases. The first line of each test case contains three integers, N, M and D (1 <= N <= 60, 1 <= M <= 150, 1 <= D <= 5), indicating the number of towns is N, the number of cables is M, and you should plan for the next D days. 

Each of the next M lines contains two integers a, b (1 <= a, b <= N), which means that Town a and Town b are connected directly. Then N lines followed, each contains two numbers si and ei, (1 <= si <= ei <= D) indicating that the available time of Town i’s power station is from the si-th day to the ei-th day (inclusive).

 

Output

For each test case, if the plan exists, output N lines. The i-th line should contain two integers ui and vi, indicating that Town i’s power station should work from the ui-th day to vi-day (inclusive). If you didn’t use this power station at all, set ui = vi = 0.

If the plan doesn’t exist, output one line contains “No solution” instead. 

Note that the answer may not be unique. Any correct answers will be OK.

Output a blank line after each case.

 

Sample Input

   
   3 3 5
1 2
2 3
3 1
1 5
1 5
1 5

4 4 5
1 2
2 3
3 4
4 1
1 5
1 5
1 5
1 5
  
  

 

Sample Output

   
   1 5
0 0
0 0

No solution
  
  

 

Source

2010 Asia Regional Harbin

 

Recommend

lcy

 

题意：有n个点，每个点是一个村庄，每个村庄都有一个发电站，每个电站可以给它所在的村庄和它有边直接连接的所有村庄供电，现在选出一些电站，使每个村庄都能被供电且每个村庄只被一个电站供电。每个村庄的发电站都只能在1-d天内的一个子区间工作，需要安排它在哪几天来工作，且每个电站一旦工作结束就不能再次启动，即它工作的时间是连续的。方案可能有多组，输出任意一组即可，无解输出No solution

解题思路：舞蹈链精确覆盖，每个城市d天都要有电供应，可以想到将列分为n*d。每个城市选择开动发电厂的时间必须连续，可将其根据对应区间分为若干行。也就是枚举开发电厂的头尾。但如果这样直接DLX会可能出现某个发电厂选多次。可以多列出n列，表示选了该发电厂。那么求一次精确覆盖后就不会出现发电厂选多次的情况了。

#include <iostream>    
#include <cstdio>    
#include <cstring>    
#include <string>    
#include <algorithm>    
#include <cctype>    
#include <map>    
#include <cmath>    
#include <set>    
#include <stack>    
#include <queue>    
#include <vector>    
#include <bitset>    
#include <functional>    

using namespace std;

#define LL long long    
const int INF = 0x3f3f3f3f;
const int maxn = 500005;

int n, m, d, x, y, tot;
int mp[100][100];
int p[1090][3], u[100], v[100];

struct DLX
{
	int L[maxn], R[maxn], U[maxn], D[maxn];
	int row[maxn], col[maxn], sum[maxn], ans[maxn];
	int n, m, num, cnt;
	void add(int k, int l, int r, int u, int d, int x, int y)
	{
		L[k] = l;   R[k] = r;   U[k] = u;
		D[k] = d;   row[k] = x;  col[k] = y;
	}
	void reset(int n, int m)
	{
		num = 0x7FFFFFF;
		this->n = n;   this->m = m;
		for (int i = 0; i <= m; i++)
		{
			add(i, i - 1, i + 1, i, i, 0, i);
			sum[i] = 0;
		}
		L[0] = m, R[m] = 0, cnt = m + 1;
	}
	void insert(int x, int y)
	{
		int temp = cnt - 1;
		if (row[temp] != x)
		{
			add(cnt, cnt, cnt, U[y], y, x, y);
			U[D[cnt]] = cnt; D[U[cnt]] = cnt;
		}
		else
		{
			add(cnt, temp, R[temp], U[y], y, x, y);
			R[L[cnt]] = cnt; L[R[cnt]] = cnt;
			U[D[cnt]] = cnt; D[U[cnt]] = cnt;
		}
		sum[y]++, cnt++;
	}
	void remove(int k)
	{
		R[L[k]] = R[k], L[R[k]] = L[k];
		for (int i = D[k]; i != k; i = D[i])
			for (int j = R[i]; j != i; j = R[j])
			{
				D[U[j]] = D[j];
				U[D[j]] = U[j];
				sum[col[j]]--;
			}
	}
	void resume(int k)
	{
		R[L[k]] = k, L[R[k]] = k;
		for (int i = D[k]; i != k; i = D[i])
			for (int j = R[i]; j != i; j = R[j])
			{
				D[U[j]] = j;
				U[D[j]] = j;
				sum[col[j]]++;
			}
	}
	bool dfs(int k)
	{
		if (!R[0]) { num = min(k, num); return true; }
		int now = R[0];
		for (int i = now; i != 0; i = R[i])
			if (sum[now] > sum[i]) now = i;
		remove(now);
		for (int i = D[now]; i != now; i = D[i])
		{
			ans[k] = row[i];
			for (int j = R[i]; j != i; j = R[j]) remove(col[j]);
			if (dfs(k + 1)) return true;
			for (int j = L[i]; j != i; j = L[j]) resume(col[j]);
		}
		resume(now);
		return false;
	}
	void display(int k)
	{
		for (int i = 0; i < num; i++)
		{
			u[p[ans[i]][0]] = p[ans[i]][1];
			v[p[ans[i]][0]] = p[ans[i]][2];
		}
		for (int i = 1; i <= k; i++) printf("%d %d\n", u[i], v[i]);
	}
}dlx;

int main()
{
	while (~scanf("%d%d%d", &n, &m, &d))
	{
		tot = 0;
		dlx.reset(n*(d*(d + 1) / 2 + 1), n * d + n);
		memset(mp, 0, sizeof mp);
		for (int i = 1; i <= m; i++)
		{
			scanf("%d%d", &x, &y);
			mp[x][y] = mp[y][x] = 1;
		}
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d", &x, &y);
			tot++;
			dlx.insert(tot, i);
			p[tot][0] = i, p[tot][1] = p[tot][2] = 0;
			for (int j = x; j <= y; j++)
			{
				for (int k = j; k <= y; k++)
				{
					tot++;
					dlx.insert(tot, i);
					p[tot][0] = i, p[tot][1] = j, p[tot][2] = k;
					for (int o = j; o <= k; o++)
						for (int pp = 1; pp<=n; pp++)
							if(mp[i][pp]||i==pp) dlx.insert(tot, (pp - 1)*d + o + n);
				}
			}
		}
		if (dlx.dfs(0)) dlx.display(n);
		else printf("No solution\n");
		putchar(10);
	}
	return 0;
}