题意方法和之前的3648基本一样
注意输出解的方式,分成两部分的点集,应该遍历其中一个点集,根据染色判断选择该点集的点还是另一个点集的点
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#define MAXN 5005
#define MAXM 50005
#define INF 1000000000
using namespace std;
int start[MAXN], end[MAXN], last[MAXN];
int n, index, scc;
vector<int>g[MAXN], dag[MAXN];
int dfn[MAXN], low[MAXN], instack[MAXN];
int fa[MAXN], ha[MAXN], color[MAXN], ind[MAXN];
queue<int>q;
stack<int>st;
void init()
{
index = scc = 0;
memset(instack, 0, sizeof(instack));
for(int i = 0; i < MAXN; i++) g[i].clear(), dag[i].clear();
memset(dfn, 0, sizeof(dfn));
memset(color, 0, sizeof(color));
memset(ind, 0, sizeof(ind));
memset(ha, 0, sizeof(ha));
while(!q.empty()) q.pop();
while(!st.empty()) st.pop();
}
bool conflict(int lx, int ly, int rx, int ry)
{
if(lx >= rx && lx <= ry) return true;
if(ly >= rx && ly <= ry) return true;
if(rx >= lx && rx <= ly) return true;
if(ry >= lx && ry <= ly) return true;
return false;
}
void build()
{
for(int i = 1; i <= n; i++)
for(int j = i + 1; j <= n; j++)
{
if(conflict(start[i], start[i] + last[i] - 1, start[j], start[j] + last[j] - 1)) g[i].push_back(j + n), g[j].push_back(i + n);
if(conflict(start[i], start[i] + last[i] - 1, end[j] - last[j] , end[j] - 1)) g[i].push_back(j), g[j + n].push_back(i + n);
if(conflict(end[i] - last[i], end[i] - 1, start[j], start[j] + last[j] - 1)) g[i + n].push_back(j + n), g[j].push_back(i);
if(conflict(end[i] - last[i], end[i] - 1, end[j] - last[j] , end[j] - 1)) g[i + n].push_back(j), g[j + n].push_back(i);
}
}
void tarjan(int u)
{
dfn[u] = low[u] = ++index;
int size = g[u].size();
int v;
instack[u] = 1;
st.push(u);
for(int i = 0; i < size; i++)
{
v = g[u][i];
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
scc++;
do
{
v = st.top();
st.pop();
instack[v] = 0;
fa[v] = scc;
}while(v != u);
}
}
void buildDag()
{
for(int u = 1; u <= 2 * n; u++)
{
int size = g[u].size();
for(int i = 0; i < size; i++)
{
int v = g[u][i];
if(fa[u] != fa[v]) dag[fa[v]].push_back(fa[u]), ind[fa[u]]++;
}
}
}
void topsort()
{
for(int i = 1; i <= scc; i++)
if(ind[i] == 0) q.push(i);
while(!q.empty())
{
int u = q.front();
q.pop();
if(!color[u]) color[u] = 1, color[ha[u]] = 2;
int size = dag[u].size();
for(int i = 0; i < size; i++)
{
int v = dag[u][i];
ind[v]--;
if(ind[v] == 0) q.push(v);
}
}
}
void solve()
{
for(int i = 1; i <= 2 * n; i++)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++)
if(fa[i] == fa[i + n])
{
puts("NO");
return;
}
else ha[fa[i]] = fa[i + n], ha[fa[i + n]] = fa[i];
buildDag();
topsort();
printf("YES\n");
for(int i = 1; i <= n; i++)
if(color[fa[i]] == 1)
{
int h1, h2, m1, m2;
h1 = start[i] / 60;
h2 = (start[i] + last[i]) / 60;
m1 = start[i] % 60;
m2 = (start[i] + last[i]) % 60;
printf("%02d:%02d %02d:%02d\n", h1, m1, h2, m2);
}
else
{
int h1, h2, m1, m2;
h1 = (end[i] - last[i]) / 60;
h2 = end[i] / 60;
m1 = (end[i] - last[i]) % 60;
m2 = end[i] % 60;
printf("%02d:%02d %02d:%02d\n", h1, m1, h2, m2);
}
}
int main()
{
int hour, miniute;
while(scanf("%d", &n) != EOF)
{
init();
for(int i = 1; i <= n; i++)
{
scanf("%d:%d", &hour, &miniute);
start[i] = hour * 60 + miniute;
scanf("%d:%d", &hour, &miniute);
end[i] = hour * 60 + miniute;
scanf("%d", &last[i]);
}
build();
solve();
}
return 0;
}
分享到:
相关推荐
POJ3211--Washing Clothes
POJ水题集-----50道左右-----增加自信啊..
POJ 1038--Bugs Integrated
POJ3036--Honeycomb Walk
POJ---1456.Supermarket测试数据及答案,题目描述:A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral ...
北大POJ初级题-数据结构:解题报告+AC代码
poj题目分类--acmer做题极有用资源
POJ3259--Wormholes,使用bellman方法。
poj 1690 Your-Term-Project.md
北大POJ3414-Pots 解题报告+AC代码
poj 1240 Pre-Post-erous!.md
北大POJ2002-Squares 解题报告+AC代码
poj 2827 Auto-Calculation Machine.md
poj平台有关数据结构题的Java源码 1159 1276 2406 2502 2509 2513 2533 2778 3176
用Java代码实现POJ(PKU)上题2494!
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
1390--blocks.rar
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
East Central North America 1999。50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50字50...