【HDU 5638 BestCoder Round 74(div 1)C】【欲張り線分ツリーorツリーカバーorキュー】Toposort n点mトポロジーを最小にしながらkを削除
11853 ワード
Toposort
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 256 Accepted Submission(s): 99
Problem Description
There is a directed acyclic graph with
n
vertices and
m
edges. You are allowed to delete exact
k
edges in such way that the lexicographically minimal topological sort of the graph is minimum possible.
Input
There are multiple test cases. The first line of input contains an integer
T
indicating the number of test cases. For each test case:
The first line contains three integers
n ,
m
and
k
(1≤n≤100000,0≤k≤m≤200000)
-- the number of vertices, the number of edges and the number of edges to delete.
For the next
m
lines, each line contains two integers
ui
and
vi , which means there is a directed edge from
ui
to
vi
(1≤ui,vi≤n) .
You can assume the graph is always a dag. The sum of values of
n
in all test cases doesn't exceed
106 . The sum of values of
m
in all test cases doesn't exceed
2×106 .
Output
For each test case, output an integer
S=(∑i=1ni⋅pi) mod (109+7) , where
p1,p2,...,pn
is the lexicographically minimal topological sort of the graph.
Sample Input
Sample Output
Source
BestCoder Round #74 (div.2)
【HDU 5638 BestCoder Round 74(div 1)C】【欲張り線分樹二分】Toposort n点mはkを削除しながらトポロジーを最小にする
【HDU 5638 BestCoder Round 74(div 1)C】【欲張りツリーセット】Toposort n点m kを削除しながらトポロジーを最小化
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 256 Accepted Submission(s): 99
Problem Description
There is a directed acyclic graph with
n
vertices and
m
edges. You are allowed to delete exact
k
edges in such way that the lexicographically minimal topological sort of the graph is minimum possible.
Input
There are multiple test cases. The first line of input contains an integer
T
indicating the number of test cases. For each test case:
The first line contains three integers
n ,
m
and
k
(1≤n≤100000,0≤k≤m≤200000)
-- the number of vertices, the number of edges and the number of edges to delete.
For the next
m
lines, each line contains two integers
ui
and
vi , which means there is a directed edge from
ui
to
vi
(1≤ui,vi≤n) .
You can assume the graph is always a dag. The sum of values of
n
in all test cases doesn't exceed
106 . The sum of values of
m
in all test cases doesn't exceed
2×106 .
Output
For each test case, output an integer
S=(∑i=1ni⋅pi) mod (109+7) , where
p1,p2,...,pn
is the lexicographically minimal topological sort of the graph.
Sample Input
3
4 2 0
1 2
1 3
4 5 1
2 1
3 1
4 1
2 3
2 4
4 4 2
1 2
2 3
3 4
1 4
Sample Output
30
27
30
Source
BestCoder Round #74 (div.2)
【HDU 5638 BestCoder Round 74(div 1)C】【欲張り線分樹二分】Toposort n点mはkを削除しながらトポロジーを最小にする
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5 + 10, M = 2e5 + 10, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m, k;
int x, y;
int ind[N];
vector<int>a[N];
// ，v ，d （ ）
int d[1 << 19];
void pushup(int o)
{
d[o] = min(d[ls], d[rs]);
}
void build(int o, int l, int r)
{
if (l == r)
{
d[o] = ind[l];
return;
}
int mid = (l + r) >> 1;
build(lson);
build(rson);
pushup(o);
}
int V;
void change(int o, int l, int r)
{
if (l == r)
{
d[o] = ind[l];
return;
}
int mid = (l + r) >> 1;
if (V <= mid)change(lson);
else change(rson);
pushup(o);
}
void check(int o, int l, int r)
{
if (l == r)
{
V = l;
d[o] = 1e9;
return;
}
int mid = (l + r) >> 1;
if (d[ls] <= k)check(lson);
else check(rson);
pushup(o);
}
int main()
{
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
{
ind[i] = 0;
a[i].clear();
}
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
++ind[y];
a[x].push_back(y);
}
build(1, 1, n);
int ans = 0;
for (LL i = 1; i <= n; ++i)
{
check(1, 1, n); x = V;
ans = (ans + i*x) % Z;
k -= ind[x];
ind[x] = 1e9;
//
for (int j = a[x].size() - 1; ~j; --j)
{
int y = a[x][j]; if (ind[y]==1e9)continue;
--ind[y];
V = y; change(1, 1, n);
}
}
printf("%d
", ans);
}
return 0;
}
/*
【 &&trick】
1， ， 1， L,R 。
check(lson) check(rson)
【 】
， n（1e5） ，m（2e5） 。 DAG
k（0<=k=m）
。
【 】
- or
【 】
， 。
。
i x， x+1。
， n 。
<=k 。
========================== ===================
。
（ 0， +1）。
。
， 。
， set 。
， 。
。
========================== ====================
。
， 。
， 。
AC
【 && 】
O(nlogn)
*/【HDU 5638 BestCoder Round 74(div 1)C】【欲張りツリーセット】Toposort n点m kを削除しながらトポロジーを最小化
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5+10, M = 2e5+10, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m, k;
int x, y;
int ind[N];
vector<int>a[N];
set<int>sot[M];
int p[N];
bool e[N];
int cnt()
{
int ret = 0;
for (LL i = 1; i <= n; ++i)ret = (ret + p[i] * i) % Z;
return ret;
}
// ，v ，d （ ）
int v[1 << 19];
int d[1 << 19];
void pushup(int o)
{
if (v[ls] < v[rs])
{
v[o] = v[ls];
d[o] = d[ls];
}
else
{
v[o] = v[rs];
d[o] = d[rs];
}
}
void build(int o, int l, int r)
{
if (l == r)
{
v[o]=sot[l].empty()?1e9:*sot[l].begin();
d[o] = l;
return;
}
int mid=(l + r) >> 1;
build(lson);
build(rson);
pushup(o);
}
int V, D, L, R;
void change(int o,int l,int r)
{
if (l == r)
{
v[o] = V;
return;
}
int mid = (l + r) >> 1;
if (D <= mid)change(lson);
else change(rson);
pushup(o);
}
void check(int o, int l, int r)
{
if (l >= L&&r <= R)
{
if (v[o] < V)
{
V = v[o];
D = d[o];
}
return;
}
int mid=(l + r) >> 1;
if (L <= mid)check(lson);
if (R > mid)check(rson);
}
int main()
{
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
{
ind[i] = 1;
a[i].clear();
}
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
++ind[y];
a[x].push_back(y);
}
if (k >= m)
{
for (int i = 1; i <= n; ++i)p[i] = i;
printf("%d
", cnt());
continue;
}
for (int i = 1; i <= n; ++i)sot[i].clear();
for (int i = 1; i <= n; ++i)sot[ind[i]].insert(i);
build(1, 1, n);
MS(e, 0);
for (int i = 1; i <= n; ++i)
{
V = 1e9; L = 1; R = k + 1;
check(1, 1, n);
int x = V; p[i] = x; e[x] = 1; //
k -= (D-1);
//
sot[D].erase(x);
V = sot[D].empty() ? 1e9 : *sot[D].begin();
change(1, 1, n);
//
for (int j = a[x].size() - 1; ~j; --j)
{
int y = a[x][j]; if (e[y])continue;
//
D = ind[y]--;
if (y == *sot[D].begin())
{
sot[D].erase(y);
V = sot[D].empty() ? 1e9 : *sot[D].begin();
change(1, 1, n);
}
else sot[D].erase(y);
//
sot[--D].insert(y);
if (y == *sot[D].begin())
{
V = y;
change(1, 1, n);
}
}
}
printf("%d
", cnt());
}
return 0;
}
/*
【 】
， n（1e5） ，m（2e5） 。 DAG
k（0<=k=m）
。
【 】
- or
【 】
， 。
。
i x， x+1。
， n 。
<=k 。
。
（ 0， +1）。
。
， 。
， set 。
， 。
。
【 && 】
O(nlogn)
*/#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5 + 10, M = 2e5 + 10, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, m, k;
int x, y;
int ind[N];
vector<int>a[N];
set<int>sot;
int main()
{
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= n; ++i)
{
ind[i] = 0;
a[i].clear();
}
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &x, &y);
++ind[y];
a[x].push_back(y);
}
for (int i = 1; i <= n; ++i)if (ind[i] <= k)sot.insert(i);
int ans = 0;
LL id = 0; while (!sot.empty())
{
int x = *sot.begin();
sot.erase(sot.begin());
if (ind[x] > k)continue;
k -= ind[x]; ind[x] = 1e9;
ans = (ans + (++id)*x) % Z;
for (int i = a[x].size() - 1; ~i; --i)
{
int y = a[x][i];
if (--ind[y] <= k)sot.insert(y);
}
}
printf("%d
", ans);
}
return 0;
}
/*
【 &&trick】
1， ， 1， L,R 。
check(lson) check(rson)
【 】
， n（1e5） ，m（2e5） 。 DAG
k（0<=k=m）
。
【 】
- or
【 】
， 。
。
i x， x+1。
， n 。
<=k 。
========================== ===================
。
（ 0， +1）。
。
， 。
， set 。
， 。
。
========================== ====================
。
， 。
， 。
AC
========================== ======================
。
<=k ，
<=k 。
O(mlog(n))
【 && 】
O(nlogn)
*/