我为什么T了。。。。
Power Stations
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2517 Accepted Submission(s): 748
Special Judge
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.
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).
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.
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
0 0
0 0
No solution
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d\n", a)
#define plld(a) printf("%lld\n", a)
#define pc(a) printf("%c\n", a)
#define ps(a) printf("%s\n", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff; int S[], head[], vis[];
int U[maxn], D[maxn], L[maxn], R[maxn];
int C[maxn], X[maxn];
int n, m, ans, ret, d; void init()
{
for(int i = ; i <= m; i++)
D[i] = i, U[i] = i, R[i] = i + , L[i] = i - ;
L[] = m, R[m] = ;
mem(S, ), mem(head, -);
ans = m + ;
} void delc(int c)
{
L[R[c]] = L[c], R[L[c]] = R[c];
for(int i = D[c]; i != c; i = D[i])
for(int j = R[i]; j != i; j = R[j])
U[D[j]] = U[j], D[U[j]] = D[j], S[C[j]]--; } void resc(int c)
{
for(int i = U[c]; i != c; i = U[i])
for(int j = L[i]; j != i; j = L[j])
U[D[j]] = j, D[U[j]] = j, S[C[j]]++;
L[R[c]] = c, R[L[c]] = c;
} void add(int r, int c)
{
ans++, S[c]++, C[ans] = c, X[ans] = r;
D[ans] = D[c];
U[ans] = c;
U[D[c]] = ans;
D[c] = ans;
if(head[r] < ) head[r] = L[ans] = R[ans] = ans;
else L[ans] = head[r], R[ans] = R[head[r]],L[R[head[r]]] = ans, R[head[r]] = ans;
} bool dfs(int sh)
{
if(!R[])
{
ret = sh;
return true;
}
int c = R[];
delc(c);
for(int i = D[c]; i != c; i = D[i])
{
vis[sh] = X[i];
for(int j = R[i]; j != i; j = R[j])
delc(C[j]);
if(dfs(sh + )) return true;
for(int j = L[i]; j != i; j = L[j])
resc(C[j]);
}
resc(c);
return false;
} int g[][];
struct node
{
int s, t, id;
}Node[], tmp[]; int main()
{ int u, v, s, t;
while(~scanf("%d%d%d", &n, &m, &d))
{
mem(g, );
for(int i = ; i < m; i++)
{
rd(u), rd(v);
g[u][v] = g[v][u] = ;
}
m = n * d + n;
init();
int cnt = ;
rap(i, , n)
{
g[i][i] = ;
rd(Node[i].s), rd(Node[i].t);
++cnt;
add(cnt, n * d + i);
tmp[cnt].s = , tmp[cnt].t = , tmp[cnt].id = i;
rap(j, Node[i].s, Node[i].t)
{
rap(k, j, Node[i].t)
{
++cnt;
add(cnt, n * d + i);
tmp[cnt].s = j, tmp[cnt].t = k, tmp[cnt].id = i;
rap(a, , n)
if(g[i][a])
rap(b, j, k)
add(cnt, (a - ) * d + b);
}
} } if(!dfs())
{
printf("No solution\n");
}
else
{
mem(X, ), mem(C, );
rep(i, , ret)
{
X[tmp[vis[i]].id] = tmp[vis[i]].s;
C[tmp[vis[i]].id] = tmp[vis[i]].t;
}
rap(i, , n)
printf("%d %d\n", X[i], C[i]);
}
printf("\n");
} return ;
}
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ; #define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define REC( i , A , o ) for ( int i = A[o] ; i != o ; i = A[i] )
#define CLR( a , x ) memset ( a , x , sizeof a ) const int MAXN = ;
const int MAXM = ;
const int MAXNODE = ; struct Node {
int l , r , idx ;
Node () {}
Node ( int l , int r , int idx ) : l ( l ) , r ( r ) , idx ( idx ) {}
} ; struct DLX {
int U[MAXNODE] , D[MAXNODE] , L[MAXNODE] , R[MAXNODE] ;
int row[MAXNODE] , col[MAXNODE] ;
int S[MAXM] , H[MAXM] ;
int deep , ans[MAXN] ;
int n , m ;
int size ; int N , M , DD ;
int X[MAXN] , Y[MAXN] ;
Node node[MAXM] ;
int G[MAXN][MAXN] ; void remove ( int c ) {
L[R[c]] = L[c] ;
R[L[c]] = R[c] ;
REC ( i , D , c )
REC ( j , R , i ) {
D[U[j]] = D[j] ;
U[D[j]] = U[j] ;
-- S[col[j]] ;
}
} void resume ( int c ) {
REC ( i , U , c )
REC ( j , L , i ) {
++ S[col[j]] ;
U[D[j]] = j ;
D[U[j]] = j ;
}
R[L[c]] = c ;
L[R[c]] = c ;
} int dance ( int d ) {
if ( R[] == ) {
deep = d ;
return ;
}
int c = R[] ;
REC ( i , R , )
if ( S[c] > S[i] )
c = i ;
//printf ( "ok\n" ) ;
remove ( c ) ;
REC ( i , D , c ) {
ans[d] = row[i] ;
REC ( j , R , i )
remove ( col[j] ) ;
if ( dance ( d + ) )
return ;
REC ( j , L , i )
resume ( col[j] ) ;
}
resume ( c ) ;
return ;
} void link ( int r , int c ) {
++ size ;
++ S[c] ;
row[size] = r ;
col[size] = c ;
U[size] = U[c] ;
D[size] = c ;
D[U[c]] = size ;
U[c] = size ;
if ( ~H[r] ) {
R[size] = H[r] ;
L[size] = L[H[r]] ;
R[L[size]] = size ;
L[R[size]] = size ;
}
else
H[r] = L[size] = R[size] = size ;
} void init () {
CLR ( H , - ) ;
FOR ( i , , n ) {
S[i] = ;
L[i] = i - ;
R[i] = i + ;
U[i] = i ;
D[i] = i ;
}
L[] = n ;
R[n] = ;
size = n ;
} void solve () {
int x , y ;
n = N * DD + N ;
m = ;
init () ;
CLR ( G , ) ;
CLR ( node , ) ;
REP ( i , , M ) {
scanf ( "%d%d" , &x , &y ) ;
G[x][y] = G[y][x] = ;
}
FOR ( i , , N )
G[i][i] = ;
FOR ( idx , , N ) {
scanf ( "%d%d" , &x , &y ) ;
int tmp = N * DD + idx ;
++ m ;
link ( m , tmp ) ;//none select
node[m] = Node ( , , idx ) ;
FOR ( i , x , y )
FOR ( j , i , y ) {
++ m ;
link ( m , tmp ) ;
node[m] = Node ( i , j , idx ) ;
FOR ( a , , N )
if ( G[idx][a] )
FOR ( b , i , j )
link ( m , ( a - ) * DD + b ) ;
}
}
if ( !dance ( ) )
printf ( "No solution\n" ) ;
else {
CLR ( X , ) ;
CLR ( Y , ) ;
REP ( i , , deep ) {
X[node[ans[i]].idx] = node[ans[i]].l ;
Y[node[ans[i]].idx] = node[ans[i]].r ;
}
FOR ( i , , N )
printf ( "%d %d\n" , X[i] , Y[i] ) ;
}
printf ( "\n" ) ;
} } dlx ; int main () {
while ( ~scanf ( "%d%d%d" , &dlx.N , &dlx.M , &dlx.DD ) )
dlx.solve () ;
return ;
}
Power Stations
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2517 Accepted Submission(s): 748
Special Judge
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.
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).
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.
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
0 0
0 0
No solution