图论专场
Fairy(CF19E)
题目大意
给出一张无向图，求删除一条边后此图变成二分图的所有删边种类 \((n\leq10^4)\)。
思路
虽然看起来 \(O(n^2)\) 能过，但其实是过不了的，我们知道，判断二分图的一种方式是判断有无奇环，所以问题变成了删去一条边后图中有无奇环，如果有环重合，可以用类似异或的逻辑将中间重复的取消，在看成一个环，明显发现只有偶环+奇环=奇环，然后就做完了。
#include<bits/stdc++.h>
#define ll long long
#define mm 10010
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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct node{
int nxt,v,id;
}e[mm<<2];
int head[mm<<2],tot=1,dfn[mm];
int n,m,ans[mm],p[mm],f[mm],Ans;
int c1[mm],c2[mm],cnt;
void ADD(int x,int y,int id)
{
e[++tot]=(node){head[x],y,id};
head[x]=tot;
}
void dfs(int x,int fa,int pre)
{
dfn[x]=dfn[fa]+1;
p[x]=e[pre].id;
for(int i=head[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
{
if((i^pre)==1)
continue;
if(!dfn[v])
{
dfs(v,x,i);
f[e[i].id]=1;
c1[e[pre].id]+=c1[e[i].id];
c2[e[pre].id]+=c2[e[i].id];
}
else
{
if(x==v && i&1)
++c1[e[i].id],++cnt;
else
{
if(dfn[x]>dfn[v])
if((dfn[x]-dfn[v])&1)
{
++c2[e[i].id];
++c2[e[pre].id];
--c2[p[v]];
}
else
{
++c1[e[i].id];
++c1[e[pre].id];
--c1[p[v]];
++cnt;
}
}
}
}
}
void print()
{
printf("%d\n",Ans);
for(int i=1;i<=Ans;i++)
printf("%d ",ans[i]);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
ADD(x,y,i);
ADD(y,x,i);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
dfs(i,0,0);
if(!cnt)
{
for(int i=1;i<=m;i++)
ans[++Ans]=i;
print();
return 0;
}
for(int i=1;i<=m;i++)
if(f[i])
{
if(c1[i]==cnt && !c2[i])
ans[++Ans]=i;
}
else
{
if(cnt==1 && c1[i]==1)
ans[++Ans]=i;
}
print();
return 0;
}
Connecting Cities(AT_keyence2019_e)
题目大意
给定 \(N\) 个点的完全图图，每个点有权值 \(A_i\)。对于任何点 \(i\) 和点 \(j\)，这两点之间的边权为 \(w_{i,j} = A_i + A_j + D|i - j|\)，其中 \(D\) 为给定的常数，求最小生成树的大小。\((N\leq 2\times 10^5,A_i,D\leq 10^9)\)
思路
还是用 \(prim\) 或 \(Kruskal\)，但这题不可以全部连边，可以发现有些边是不必要的，先考虑把式子简化，我们如果确定这两个 \(i\) 和 \(j\)，可以变成 \(A_i+D\times i+A_j-D\times j\)。
既然 \(i\) 和 \(j\) 独立出来，那么只需要选出，右半部分 \(min{A_i+D\times i}\) 所对应的 \(i\)，左半部分 \(min{A_j+D\times j}\) 所对应的 \(j\)，将 \(j\) 与右半部分所有点连边，\(i\) 同理，这样边就只有 \(O(nlog_n)\)，最后跑 \(Kruskal\)。
#include<bits/stdc++.h>
#define ll long long
#define mm 10010
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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
struct node{
int nxt,v,id;
}e[mm<<2];
int head[mm<<2],tot=1,dfn[mm];
int n,m,ans[mm],p[mm],f[mm],Ans;
int c1[mm],c2[mm],cnt;
void ADD(int x,int y,int id)
{
e[++tot]=(node){head[x],y,id};
head[x]=tot;
}
void dfs(int x,int fa,int pre)
{
dfn[x]=dfn[fa]+1;
p[x]=e[pre].id;
for(int i=head[x],v=e[i].v;i;i=e[i].nxt,v=e[i].v)
{
if((i^pre)==1)
continue;
if(!dfn[v])
{
dfs(v,x,i);
f[e[i].id]=1;
c1[e[pre].id]+=c1[e[i].id];
c2[e[pre].id]+=c2[e[i].id];
}
else
{
if(x==v && i&1)
++c1[e[i].id],++cnt;
else
{
if(dfn[x]>dfn[v])
if((dfn[x]-dfn[v])&1)
{
++c2[e[i].id];
++c2[e[pre].id];
--c2[p[v]];
}
else
{
++c1[e[i].id];
++c1[e[pre].id];
--c1[p[v]];
++cnt;
}
}
}
}
}
void print()
{
printf("%d\n",Ans);
for(int i=1;i<=Ans;i++)
printf("%d ",ans[i]);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
ADD(x,y,i);
ADD(y,x,i);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
dfs(i,0,0);
if(!cnt)
{
for(int i=1;i<=m;i++)
ans[++Ans]=i;
print();
return 0;
}
for(int i=1;i<=m;i++)
if(f[i])
{
if(c1[i]==cnt && !c2[i])
ans[++Ans]=i;
}
else
{
if(cnt==1 && c1[i]==1)
ans[++Ans]=i;
}
print();
return 0;
}
Tournament(CF878C)
题目大意
有 \(n\) 个人，每个人都有 \(k\) 种能力值 \(a_{i,1}，a_{i,2}……a_{i,k}\)。
定义淘汰赛的规则如下：在没被淘汰的人中选出两个 \(i\) 和 \(j\)，并选择 \(d\in [1,k]\)。如果 \(a_{i,d} > a_{j,d}\)，则 \(j\) 淘汰；否则 \(i\) 淘汰（保证所有的 \(a_{i,d}\) 互不相同）。直到只剩下一个人没有被淘汰，则这个人是最终的胜者。
对于每个 \(i\)，需要求出如果初始参加比赛的人是 \(1,2,...,i\)，这 \(i\) 个人里有多少人可能成为最终的胜者。
\(n\leq 5\times 10^4,k\leq 10\)
思路
我们考虑两个选手之间的关系，如果一个选手能在某一项运动中战胜对手，那么就从他自身向对手连一条有向边。这样显然会出现很多环，于是可以缩点，将整张图缩成一条链。那么显然入度为零的环中包含的点数即为最后可能成为冠军的人数。
#include<bits/stdc++.h>
#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<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}
int n,k;
struct node{
int siz;
int maxn[15],minn[15];
node(){
memset(maxn,0,sizeof(maxn));
memset(minn,0x3f,sizeof(minn));
}
friend bool operator <(node a,node b){
for(int i=1;i<=k;i++)
if(a.maxn[i]>b.minn[i])
return false;
return true;
}
};
set<node> s;
set<node>::iterator it;
int main()
{
n=read(),k=read();
node t;
for(int i=1;i<=n;i++)
{
t.siz=1;
for(int j=1;j<=k;j++)
t.maxn[j]=t.minn[j]=read();
while((it=s.find(t))!=s.end())
{
t.siz+=it->siz;
for(int j=1;j<=k;j++)
{
t.minn[j]=min(t.minn[j],it->minn[j]);
t.maxn[j]=max(t.maxn[j],it->maxn[j]);
}
s.erase(it);
}
s.insert(t);
printf("%d\n",(--s.end())->siz);
}
return 0;
}