「BC35」DZY Loves Topological Sorting

2015年3月30日3,2670

问题描述

一张有向图的拓扑序列是图中点的一个排列，满足对于图中的每条有向边(u→v) 从 u 到 v，都满足u在排列中出现在v之前。现在，DZY有一张有向无环图(DAG)。你要在最多删去k条边之后，求出字典序最大的拓扑序列。

输入描述

输入有多组数据。 (TestCase≤5) 第一行，三个正整数 n,m,k(1≤n,m≤105,0≤k≤m). 接下来m行，每行两个正整数 u,v(u≠v,1≤u,v≤n), 代表一条有向边(u→v).

输出描述

对于每组测试数据，输出一行字典序最大的拓扑序列。

输入样例

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

输出样例

5 3 1 2 4 1 3 2

Hint

数据1. 删除(2->3),(4->5)两条边，可以得到字典序最大的拓扑序列：(5,3,1,2,4).

题解

搬运官方题解

因为我们要求最后的拓扑序列字典序最大，所以一定要贪心地将标号越大的点越早入队。我们定义点i的入度为di。假设当前还能删去k条边，那么我们一定会把当前还没入队的di≤k的最大的i找出来，把它的di条入边都删掉，然后加入拓扑序列。可以证明，这一定是最优的。具体实现可以用线段树维护每个位置的di，在线段树上二分可以找到当前还没入队的di≤k的最大的i。于是时间复杂度就是O((n+m)logn).

蒟蒻hzwer用了个堆来暴力。。。

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int 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;
}
bool flag;
int n,m,K,cnt;
int last[100005],d[100005];
bool vis[100005];
struct edge{
    int to,next;
}e[100005];
priority_queue<int,vector<int> >q;
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void del(int x)
{
    if(!flag)printf("%d",x);
    else printf(" %d",x);
    flag=1;
    for(int i=last[x];i;i=e[i].next)
    {
        d[e[i].to]--;
        if(d[e[i].to]<=K&&!vis[e[i].to])
        {
            q.push(e[i].to);
            vis[e[i].to]=1;
        }
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&K)!=EOF)
    {
        flag=0;
        memset(last,0,sizeof(last));cnt=0;
        memset(d,0,sizeof(d));
        memset(vis,0,sizeof(vis));
        for(int i=1;i<=m;i++)
        {
            int u=read(),v=read();
            insert(u,v);
            d[v]++;
        }
        for(int i=n;i>=1;i--)
            if(d[i]<=K)
            {
                q.push(i);vis[i]=1;
            }
        while(!q.empty())
        {
            int t=q.top();q.pop();
            if(K>=d[t])K-=d[t],del(t);
            else vis[t]=0;
        }
        puts("");
    }
    return 0;
}

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int 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;

}

bool flag;

int n,m,K,cnt;

int last[100005],d[100005];

bool vis[100005];

struct edge{

int to,next;

}e[100005];

priority_queue<int,vector<int> >q;

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void del(int x)

{

if(!flag)printf("%d",x);

else printf(" %d",x);

flag=1;

for(int i=last[x];i;i=e[i].next)

{

d[e[i].to]--;

if(d[e[i].to]<=K&&!vis[e[i].to])

{

q.push(e[i].to);

vis[e[i].to]=1;

}

int main()

{

while(scanf("%d%d%d",&n,&m,&K)!=EOF)

{

flag=0;

memset(last,0,sizeof(last));cnt=0;

memset(d,0,sizeof(d));

memset(vis,0,sizeof(vis));

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

insert(u,v);

d[v]++;

}

for(int i=n;i>=1;i--)

if(d[i]<=K)

{

q.push(i);vis[i]=1;

}

while(!q.empty())

{

int t=q.top();q.pop();

if(K>=d[t])K-=d[t],del(t);

else vis[t]=0;

}

puts("");

}

return 0;

}

« 「BZOJ3850」ZCC Loves Codefires 「East!_XVI」不祥之刃 »

hzwer.com _ Home | http://hzwer.com

「BC35」DZY Loves Topological Sorting

分类目录

热门文章

Myfriends

近期评论