今天是\(JSOI2010\)专场
T1满汉全席（2-SAT）
比较生疏的知识点，当时看着一眼就觉得是图论，甚至想到了最大流，但是因为建不来图，被迫去打了暴力,然而只得到\(10pts\)，事实证明我的想法是正确的，但是太菜了。
关于\(2-SAT\)
这类问题就是对于\(n\)个不同的命题，存在命题\(a,b\)，若\(a\)不成立，那么\(b\)就必须成立(反之亦然)。
举个例子
有三对夫妻\(ai,bi\)要参加舞会，每对夫妻至少有一人参加，是否存在一种方案使得题意被满足。建立状态\(0,1\)表示参加和不参加，已知有一些夫妻之间存在矛盾，例如\(a1,b2\)不能同时存在，即\(a1\)参加（\(1\)）\(b2\)就不能参加(\(0\))，就可以用建图和\(tarjan\)求强连通分量、或者是\(dfs\)来解决建图后的问题。
根据以上性质，在这个例子中我们可以从\(a1\)的\(1\)状态向\(b2\)的\(0\)状态连一条有向边，再从\(a1\)的\(0\)状态向\(b2\)的\(1\)状态连另一条有向边，这样我们就成功地描述了事情之间的因果逻辑。
解决问题
在建好图以后，怎么处理这样一条条的逻辑关系呢？我们可以使用\(tarjan\)求强联通分量的算法，为什么呢？因为这些逻辑关系实际上就是单向的“导致”，在一个强连通分量内，所有命题必须同时存在，如果有两个互斥的条件同时存在于一个\(SCC\)中，那么就是不能满足的。
同理在这个题里，如果一个评委的要求\(1\)不能被满足，那么要求\(2\)就是必须被满足的，所以我们建边的方式就有了，之后的\(tarjan\)照着打就行了，只是多组数据记得该重置的要重置（特别是head[maxn]数组！！）
点击查看代码
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
const int maxn=2e4+10;
int n,m;
struct Edge{int u,v;int nex;}E[maxn];
int tote=0;int head[maxn];
void add(int u,int v)
{
E[++tote].u=u,E[tote].v=v;
E[tote].nex=head[u];head[u]=tote;
}
int dfn[maxn],low[maxn],cnt=0,s[maxn]/*栈*/,ins[maxn],top;
int scc[maxn],num=0; // 结点 i 所在 SCC 的编号、当前的scc个数
void tarjan(int x)
{
low[x]=dfn[x]=++cnt;
s[++top]=x;ins[x]=1;
for(int i=head[x];i;i=E[i].nex)
{
int v=E[i].v;
if(!dfn[v])
{
tarjan(v);
low[x]=min(low[x], low[v]);
}
else if(ins[v])
low[x]=min(low[x],dfn[v]);
}
if(dfn[x]==low[x])
{
++num;
while(s[top]!=x)
{
scc[s[top]]=num;
ins[s[top]]=0;
top--;
}
scc[s[top]]=num;
ins[s[top]]=0;
--top;
}
}
void reset()
{
memset(head,0,sizeof head);
memset(dfn,0,sizeof dfn);
memset(low,0,sizeof low);
memset(ins,0,sizeof ins);
memset(s,0,sizeof s);
top=tote=cnt=num=0;
}
inline int read()
{
int x=0,f=1;
char c=getchar();
while('0'>c||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
//1~n 'm' n+1~2n 'h'
char tmp1[10],tmp2[10];
void trans(char a1[],char a2[])
{
int c1=0,c2=0;
for(int i=1;i<strlen(a1);i++)
c1=c1*10+a1[i]-'0';
for(int i=1;i<strlen(a2);i++)
c2=c2*10+a2[i]-'0';
add(a1[0]=='m'?c1+n:c1,a2[0]=='m'?c2:c2+n);
}
int main()
{
int t=read();
while(t--)
{
reset();
n=read(),m=read();
for(int i=1;i<=m;i++)
{
scanf("%s %s",tmp1,tmp2);
trans(tmp1,tmp2),trans(tmp2,tmp1);
}
for(int i=1;i<=n*2;i++)if(!dfn[i])tarjan(i);
int flag=0;
for(int i=1;i<=n;i++)
{
if(scc[i]==scc[i+n])
{
flag=1;
break;
}
}
if(flag==1)puts("BAD");
else puts("GOOD");
}
return 0;
}
/*
2
3 4
m3 h1
m1 m2
h1 h3
h3 m2
2 4
h1 m2
m2 m1
h1 h2
m1 h2
*/
T2部落划分
一眼最小生成树（传统艺能了）
连一条有效边就让集合减少1个，初始n个，目标k个，所以只用连n-k个就行，连完了n-k个边后，下一个可以合并集合的边就是要求的答案了
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
double calc(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
int n,k;int x,y;
struct Edge{int u,v;double w;}E[maxn];int tote;
struct point{int x;int y;}p[maxn];
bool cmp(Edge a,Edge b){return a.w<b.w;}
int f[maxn];
int find(int x){return x==f[x]?x:f[x]=find(f[x]);}
inline int read()
{
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<1)+(x<<3)+(c^48);
c=getchar();
}
return x*f;
}
int main()
{
freopen("group.in","r",stdin);
freopen("group.out","w",stdout);
scanf("%d%d",&n,&k);
for(int i=1;i<=n;i++)p[i].x=read(),p[i].y=read(),f[i]=i;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
E[++tote].u=i,E[tote].v=j,E[tote].w=calc(p[i].x,p[i].y,p[j].x,p[j].y);
sort(E+1,E+tote+1,cmp);
int cnt=0;int flag=0;
for(int i=1;i<=tote;i++)
{
if(cnt==n-k)
{
flag=1;
}
int x=find(E[i].u),y=find(E[i].v);
if(x!=y)
{
cnt++;
if(flag==1)
{
printf("%.2lf",E[i].w);
break;
}
f[x]=y;
}
}
return 0;
}
/*
4 2
0 0
0 1
1 1
1 0
1.00
*/
/*
9 3
2 2
2 3
3 2
3 3
3 5
3 6
4 6
6 2
6 3
2.00
*/
T3冷冻波
明天再来打
T4蔬菜庆典
明天再来打
标签：21,tote,int,top,dfn,maxn,low,2022.09,Test From： https://www.cnblogs.com/Hanggoash/p/16717192.html