hdu 5195 DZY Loves Topological Sorting 线段树+拓扑排序
DZY Loves Topological SortingTime Limit: 1 Sec Memory Limit: 256 MB题目连接
http://acm.hdu.edu.cn/showproblem.php?pid=5195
Description
A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge (u→v) from vertex u to vertex v, u comes before v in the ordering.
Now, DZY has a directed acyclic graph(DAG). You should find the lexicographically largest topological ordering after erasing at most k edges from the graph.
Input
The input consists several test cases. (TestCase≤5)
The first line, three integers n,m,k(1≤n,m≤105,0≤k≤m).
Each of the next m lines has two integers: u,v(u≠v,1≤u,v≤n), representing a direct edge(u→v).
Output
For each test case, output the lexicographically largest topological ordering.
Sample Input
5 5 2
1 2
4 5
2 4
3 4
2 3
3 2 0
1 2
1 3
Sample Output
5 3 1 2 4
1 3 2
HINT
题意
一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v) 从 u 到 v，都满足u在排列中出现在v之前。
现在，DZY有一张有向无环图(DAG)。你要在最多删去k条边之后，求出字典序最大的拓扑序列。
题解：
因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。假设当前还能删去k条边，那么我们一定会把当前还没入队的di≤k的最大的i找出来，把它的di条入边都删掉，然后加入拓扑序列。可以证明，这一定是最优的。
具体实现可以用线段树维护每个位置的di，在线段树上二分可以找到当前还没入队的di≤k的最大的i。于是时间复杂度就是O((n+m)logn).
代码：
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 200001
#define mod 10007
#define eps 1e-9
int Num;
char CH;
//const int inf=0x7fffffff; //нчоч╢С
const int inf=0x3f3f3f3f;
/*
inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH+48);
puts("");
}
*/
//**************************************************************************************
inline ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=0;if(!x){putchar('0');puts("");return;}
while(x>0)CH[++Num]=x%10,x/=10;
while(Num)putchar(CH+48);
puts("");
}
int du;
int vis;
vector<int> lin;
int n,m,k;
int t;
int arr;
void build(int i,int l,int r)
{
if (l==r)
{
t=du;
arr=i;
return;
}
int mid=(l+r)/2;
build(i*2,l,mid);
build(i*2+1,mid+1,r);
t=min(t,t);
return;
}
int query(int i,int l,int r,int k)
{
if (l==r)
return l;
int mid=(l+r)/2;
if (t<=k) return query(i*2+1,mid+1,r,k);
else return query(i*2,l,mid,k);
}
void insert(int i,int l,int r,int wei,int cc)
{
if (l==r)
{
t+=cc;
return;
}
int mid=(l+r)/2;
if (wei<=mid) insert(i*2,l,mid,wei,cc);
else insert(i*2+1,mid+1,r,wei,cc);
t=min(t,t);
return;
}
int main()
{
while (cin>>n>>m>>k)
{
memset(vis,0,sizeof(vis));
memset(du,0,sizeof(du));
for (int i=1;i<=n;i++)
lin.clear();
int i,j;
for (int tt=1;tt<=m;tt++)
{
scanf("%d%d",&i,&j);
lin.push_back(j);
du++;
}
int nn=0;
int flag=0;
build(1,1,n);
for (int i=1;i<=n;i++)
{
int c=query(1,1,n,k);
if (flag) printf(" ");
printf("%d",c);
flag=1;
k-=du;
insert(1,1,n,c,9999999);
for (int kk=0;kk<lin.size();kk++)
{
int j=lin;
insert(1,1,n,j,-1);
du--;
}
}
printf("\n");
}
}
文档来源：51CTO技术博客https://blog.51cto.com/u_15303184/3111738
页:
[1]