Wuyanru's blog
0%

[ARC161F] Everywhere is Sparser than Whole (Judge)

发表于 分类于 ，

完全看不出来是这做法啊。

题目链接。

题意

定义一张图的密度为 。

给定一张密度恰好为 的图。

问是否有，所有非空真导出子图密度均有 。

。

题解

考虑先判断是否有子图密度 。

可以发现 等价于 。

意思就是说，选一条边有 的收益，选一个点有 的代价，如果选择一条边，就必须要选择它的两个端点。

现在问我们是否有收益 的方案。

容易发现，这是一个最大权闭合子图问题，可以使用网络流解决。

建出图后发现，这是一个二分图，所以这部分复杂度是 。

那么问题在于，如何判断有子图密度恰好为 。

看看我们上面的流跑出了什么，我们发现一个点恰好匹配了 条边。

那么我们考虑给每一条边定向，使得每一个点出度恰好是 。

  1. 当这张图有不止一个强连通分量时：

    那么一定存在一个没有出度的强连通分量，我们选中这个强连通分量。

    容易发现这个子图密度恰好是 ，说明整张图不合法。

  2. 当这张图有一个导出真子图密度是 的时候：

    一定存在一种给边定向的方式，使得这些点构成了一组强连通分量，并且这个强连通分量出度是 。

    然后你考虑别的定向方式，容易发现所有定向方式这些点一定都是形成强连通分量。

    因为你考虑这个强连通分量的入度，如果边的方向变了，那么原来那个强连通分量出度就爆了，怎么都分不出去。

    所以无论怎么给边定向，这些点始终形成强连通分量。

这样我们就证明了，存在密度为 的导出真子图，当且仅当这张图定向之后，有不止一个强连通分量。

这样就只需要跑完流之后跑一个 tarjan 就行。

时间复杂度 。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
struct node
{
    int u,v;
}e[50001];
vc<int>rg[50001];
vc<int>g[50001];
bool vis[50001];
int rk[50001];
int head[100005];
int cur[100005];
int dis[100005];
int gap[100005];
int nx[400005];
int to[400005];
int w[400005];
int d,n,s,t,m,C;
inline void ad(int u,int v,int ww)
{
    m++,to[m]=v,w[m]=ww;
    nx[m]=head[u],head[u]=m;
}
inline void add(int u,int v,int w)
{
    ad(u,v,w);
    ad(v,u,0);
}
inline void bfs()
{
    dis[t]=1,gap[1]++;
    queue<int>que;que.push(t);
    while(!que.empty())
    {
        int u=que.front();que.pop();
        for(int i=head[u];i;i=nx[i]) if(w[i^1])
        {
            int p=to[i];
            if(dis[p]==-1)
            {
                dis[p]=dis[u]+1,gap[dis[p]]++;
                que.push(p);
            }
        }
    }
}
inline int dfs(int u,int flow)
{
    if(u==t) return flow;
    int rest=flow;
    for(int &i=cur[u];i;i=nx[i])
    {
        int p=to[i];
        if(!w[i]||dis[p]+1!=dis[u]) continue;
        int num=dfs(p,min(rest,w[i]));
        w[i]-=num,w[i^1]+=num,rest-=num;
        if(!rest) return flow;
    }
    if(!(--gap[dis[u]])) dis[s]=t+1;
    gap[++dis[u]]++;
    return flow-rest;
}
inline int ISAP()
{
    memset(dis,-1,sizeof(int)*(t+1));
    memset(gap,0,sizeof(int)*(t+1));
    bfs();

    int ans=0;
    while(dis[s]<=t)
    {
        memcpy(cur,head,sizeof(int)*(t+1));
        ans+=dfs(s,0x3f3f3f3f);
    }
    return ans;
}
void dfs1(int num)
{
    vis[num]=1;
    for(int p:g[num]) if(!vis[p]) dfs1(p);
    rk[++C]=num;
}
void dfs2(int num)
{
    vis[num]=1;
    for(int p:rg[num]) if(!vis[p]) dfs2(p);
}
inline void solve()
{
    n=read(),d=read();s=n*(d+1)+1,t=s+1;
    memset(head,0,sizeof(int)*(t+1)),m=1;
    for(int i=1;i<=n*d;i++)
    {
        e[i].u=read(),e[i].v=read();
        add(i+n,e[i].u,0x3f3f3f3f);
        add(i+n,e[i].v,0x3f3f3f3f);
        add(s,i+n,1);
    }
    for(int i=1;i<=n;i++)
    {
        add(i,t,d);
        g[i].clear(),rg[i].clear();
    }
    int V=ISAP();
    if(V!=n*d)
    {
        printf("No\n");
        return ;
    }

    for(int i=1;i<=n;i++) for(int j=head[i];j;j=nx[j]) if(w[j])
    {
        int id=to[j]-n;
        g[i].push_back(e[id].u+e[id].v-i);
        rg[e[id].u+e[id].v-i].push_back(i);
    }

    memset(vis,0,sizeof(bool)*(n+1)),C=0;
    for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i);
    memset(vis,0,sizeof(bool)*(n+1)),C=0;
    for(int i=n;i;i--) if(!vis[rk[i]]) dfs2(rk[i]),C++;

    if(C==1) printf("Yes\n");
    else printf("No\n");
}
int main()
{
    int T=read();
    while(T--) solve();
    return 0;
}