POI2012
T1 Festival 首先差分构图，然后可以进行缩点，这样不同强连通分量互不影响，在每个强连通分量中求出最大的绝对值+1即为该强连通分量的贡献，如果有正环则无解
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 610
#define M 200020
#define inf -0x3f3f3f3f
using namespace std;
int n,m1,m2,i,j,x,y,tot,top,sz,cnt,now,ans,z[N],d[N][N],fir[N],st[N],low[N],dfn[N],bl[N],la[M],va[M],ne[M];bool is[N];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(int x,int y){return bl[x]<bl[y];}
void tarjan(int x){
low[x]=dfn[x]=++sz;is[x]=1;st[++top]=x;int y,i;
for(i=fir[x];i;i=ne[i])if(!dfn[y=la[i]])tarjan(y),low[x]=min(low[x],low[y]);else if(is[y])low[x]=min(low[x],dfn[y]);
if(dfn[x]==low[x])for(cnt++,now=0;now!=x;now=st[top--],bl[now]=cnt,is[now]=0);
}
int main(){
for(scanf("%d%d%d",&n,&m1,&m2);m1--;)scanf("%d%d",&x,&y),ins(x,y,1),ins(y,x,-1);
for(;m2--;)scanf("%d%d",&x,&y),ins(x,y,0);memset(d,inf,sizeof(d));
for(i=1;i<=n;d[i][i]=0,z[i]=i++)if(!dfn[i])tarjan(i);
for(x=1;x<=n;x++)for(i=fir[x];i;i=ne[i])if(bl[x]==bl[la[i]])d[x][la[i]]=max(d[x][la[i]],va[i]);
for(x=1;x<=n;x++)for(i=1;i<=n;i++)if(d[i][x]!=inf)for(j=1;j<=n;j++)if(d[x][j]!=inf)d[i][j]=max(d[i][j],d[i][x]+d[x][j]);
for(i=1;i<=n;i++)if(d[i][i]>0)return puts("NIE"),0;sort(z+1,z+n+1,cmp);
for(x=1;x<=n;ans+=now+1,x=y){
for(y=x;y<=n&&bl[z[x]]==bl[z[y]];y++);
for(now=0,i=x;i<y;i++)for(j=x;j<y;j++)now=max(now,abs(d[z[i]][z[j]]));
}
printf("%d",ans);
}
T2 Letters 首先一个想法是相同字母的相对顺序不会改变，于是可以得知目标串每个字母在原串中的位置，然后答案就是这个的逆序对
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
int n,i,x,sum,now,c[1001000];
queue<int>q[26];char s[1001000];long long ans;
void add(int x){for(;x<=n;x+=x&-x)c[x]++;}
long long que(int x){for(now=0;x;x-=x&-x)now+=c[x];return now;}
int main(){
for(scanf("%d%s",&n,s+1),i=1;i<=n;i++)q[s[i]-'A'].push(i);
for(scanf("%s",s+1),i=1;i<=n;i++){
x=q[s[i]-'A'].front();q[s[i]-'A'].pop();
add(n-x+1);ans+=que(n-x);
}printf("%lld",ans);
}
T3 Distance 先$O(n)$线性筛扫出每个数的因数个数，然后要求每个数的$min(d[i]+d[j]-2*d[gcd(i,j)])$，枚举这个因数，再加上是这个因数倍数的b[i]的最小值即可，由于可能这个最小值就是该数，还要统计一个次小值，时间复杂度$O(n\sqrt{n})$
#include<cstdio>
#include<cstring>
#define N 1001000
int n,i,j,x,w,t,u,d1[N],d2[N],e1[N],e2[N],b[N],p[N],a[N];bool f[N];
void cg(int x,int y,int z){if(z<d1[x]||z==d1[x]&&y<e1[x])d2[x]=d1[x],e2[x]=e1[x],d1[x]=z,e1[x]=y;else if(y!=e1[x]&&(z<d2[x]||z==d2[x]&&y<e2[x]))d2[x]=z,e2[x]=y;}
void get(int z,int y){if(z<w||z==w&&y<u)w=z,u=y;}
void r(int j){get(e1[j]==i?d2[j]-2*b[j]:d1[j]-2*b[j],e1[j]==i?e2[j]:e1[j]);}
int main(){
for(memset(d1,63,sizeof(d1)),memset(d2,63,sizeof(d2)),i=2;i<=1000000;i++){
if(!f[i])p[++t]=i,b[i]=1;
for(j=1;j<=t&&i*p[j]<=1000000;j++){
f[i*p[j]]=1;b[i*p[j]]=b[i]+1;
if(i%p[j]==0)break;
}
}
for(scanf("%d",&n),i=1;i<=n;i++){
scanf("%d",&a[i]);
for(j=1;j*j<=a[i];j++)if(a[i]%j==0){
cg(j,i,b[a[i]]);
if(a[i]*a[i]!=j)cg(a[i]/j,i,b[a[i]]);
}
}
for(i=1;i<=n;printf("%d\n",u),i++)for(w=1e9,j=1;j*j<=a[i];j++)if(a[i]%j==0)r(j),r(a[i]/j);
}
T4 Rendezvous 基环树上求LCA，如果在一棵外向树上直接求，否则判断走环两边的距离，取更优的作为答案
#include<cstdio>
#include<algorithm>
#define N 500500
using namespace std;
int n,Q,i,j,top,tm,tmp,x,y,t,x1,y1,x2,y2,to[N],pos[N],rt[N],v[N],bl[N],sz[N],h[N],fa[N][20];
void fcur(int x){
v[x]=tm;int y;
if(v[to[x]]==tm){
for(y=x,tmp=0;!tmp||x!=y;y=to[y],tmp++)bl[y]=tm,pos[y]=tmp,rt[y]=y;
sz[tm]=tmp;return;
}
if(!v[to[x]])fcur(to[x]);
if(!bl[x])fa[x][0]=to[x],h[x]=h[to[x]]+1,rt[x]=rt[to[x]];
}
int lca(int x,int y){
if(h[x]<h[y])swap(x,y);
int t=h[x]-h[y],i;
for(i=0;i<=19;i++)if(t&(1<<i))x=fa[x][i];
for(i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return x==y?x:fa[x][0];
}
int dis(int x,int y,int p){return (y-x+p)%p;}
int main(){
for(scanf("%d%d",&n,&Q),i=1;i<=n;i++)scanf("%d",&to[i]);
for(i=1;i<=n;i++)if(!v[i])tm++,fcur(i);
for(j=1;j<=19;j++)for(i=1;i<=n;i++)fa[i][j]=fa[fa[i][j-1]][j-1];
for(;Q--;){
scanf("%d%d",&x,&y);
if(bl[rt[x]]!=bl[rt[y]]){puts("-1 -1");continue;}
if(rt[x]==rt[y]){
t=lca(x,y);
printf("%d %d\n",h[x]-h[t],h[y]-h[t]);
continue;
}
x1=h[x]+dis(pos[rt[x]],pos[rt[y]],sz[bl[rt[x]]]);y1=h[y];
x2=h[x];y2=h[y]+dis(pos[rt[y]],pos[rt[x]],sz[bl[rt[y]]]);
if(max(x1,y1)<max(x2,y2))printf("%d %d\n",x1,y1);else
if(max(x2,y2)<max(x1,y2))printf("%d %d\n",x2,y2);else
if(min(x1,y1)<min(x2,y2))printf("%d %d\n",x1,y1);else
if(min(x2,y2)<min(x1,y1))printf("%d %d\n",x2,y2);else
printf("%d %d\n",max(x1,y1),min(x1,y1));
}
}
T5 Well 首先很容易想到二分，难点在于如何快速判断是否合法
可以先从左往右扫一遍，再从右往左扫一遍，把差距调到mid以内
然后枚举每个位置变为0，则他对答案的影响是左边和右边各一个等差数列，因为是单调的，可以顺序扫一遍得出每个位置改为0的代价
这样总的时间复杂度是$O(nlgn)$的
#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;typedef long long LL;
int n,i,j,l,r,mid,t,z,k,a[N],b[N];LL m,now,s[N],f[N];
int ok(int w){
for(b[1]=a[1],i=2;i<=n;i++)b[i]=min(a[i],b[i-1]+w);
for(i=n-1;i;i--)b[i]=min(b[i],b[i+1]+w);
for(now=0,i=1;i<=n;i++)now+=a[i]-b[i],s[i]=s[i-1]+b[i];
for(i=j=1;i<=n;i++){
for(;j<i&&b[j]<=(LL)(i-j)*w;j++);
f[i]=s[i-1]-s[j-1]-(LL)(1+i-j)*(i-j)*w/2;
}
for(i=j=n;i;i--){
for(;j>i&&b[j]<=(LL)(j-i)*w;j--);
f[i]+=s[j]-s[i]-(LL)(1+j-i)*(j-i)*w/2;
}
for(i=1;i<=n;i++)if(f[i]+b[i]+now<=m)return i;return 0;
}
int main(){
for(scanf("%d%lld",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]),r=r>a[i]?r:a[i];
while(l<=r)if(t=ok(mid=(l+r)>>1))r=(z=mid)-1,k=t;else l=mid+1;
printf("%d %d",k,z);
}
T6 Vouchers 因为知道这是一道傻逼题，就往傻逼的地方想，觉得暴力取应该没什么问题，是一个调和级数的复杂度，但由于姿势不太对WA了好几发
#include<cstdio>
#define N 1001000
int m,i,n,x,p,t,now,q[N],u[N];bool v[N],s[N];
long long a[N],top;
int main(){
for(scanf("%d",&m),i=1;i<=m;i++)scanf("%d",&x),s[x]=1;
for(scanf("%d",&n),i=1;i<=n;i++){
scanf("%d",&x);
for(now=0,p=u[x]+x;p<=1000000&&now<x;p+=x)if(!v[p]){
++top;v[p]=1;now++;
if(s[p])a[++t]=top;
}
top+=x-now;u[x]=p-x;
}
for(printf("%d\n",t),i=1;i<=t;i++)printf("%lld\n",a[i]);
}
T7 Cloakroom 凑来凑去感觉只有$O(nk)$才有些许希望，于是可以把每个物品和询问按左端点排序，然后当物品左端点小于等于询问左端点时进行一次背包，dp的值表示和为这个价值时右端点较小值中的最大值，这样的时间复杂度是$O(nk+qlgq+nlgn)$的，能卡过去
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1010
using namespace std;
int n,i,Q,t,j,ans[N*N],dp[N*N];
struct E{int c,l,r;}e[N];struct U{int l,k,r,z;}q[N*N];
bool cmp(E a,E b){return a.l<b.l;}bool Cmp(U a,U b){return a.l<b.l;}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d%d%d",&e[i].c,&e[i].l,&e[i].r);sort(e+1,e+n+1,cmp);
for(scanf("%d",&Q),i=1;i<=Q;i++)scanf("%d%d%d",&q[i].l,&q[i].k,&q[i].r),q[i].r+=q[i].l+1,q[i].z=i;
sort(q+1,q+Q+1,Cmp);memset(dp,-1,sizeof(dp));dp[0]=2e9;
for(t=i=1;i<=Q;i++){
for(;e[t].l<=q[i].l&&t<=n;t++)
for(j=100001;j>=e[t].c;j--)dp[j]=max(dp[j],min(dp[j-e[t].c],e[t].r));
ans[q[i].z]=(dp[q[i].k]>=q[i].r);
}
for(i=1;i<=Q;i++)puts(ans[i]?"TAK":"NIE");
}
T8 A Horrible Poem 首先可以用哈希$O(1)$判断长度$x$是否是$l~r$的循环节，只要判$l~(r-x)$和$(l+x)~r$是否相等就行了，但如果暴力判时间复杂度是$O(n\sqrt{N})$会T，可以先枚举出所有质数，然后如果$x$是$l~r$的循环节，那么最小循环节一定是$x$的约数，于是可以枚举所有质因子，不断除去就可以在$O(nlgn)$时间内出解
#include<cstdio>
#define S 1000000007
#define N 500500
typedef unsigned long long LL;
int n,Q,i,j,p,len,x,y,z,to[N],prime[N];char s[N];LL a[N],pow[N];
bool ck(int l1,int r1,int l2,int r2){return a[r1]-a[l1-1]*pow[r1-l1+1]==a[r2]-a[l2-1]*pow[r2-l2+1];}
int main(){
for(scanf("%d%s%d",&n,s+1,&Q),pow[0]=1,i=1;i<=n;i++)pow[i]=pow[i-1]*S,a[i]=a[i-1]*S+(s[i]-'a'+1);
for(i=2;i<=n;i++){
if(!to[i])to[i]=prime[++p]=i;
for(j=1;j<=p&&i*prime[j]<=n;j++){
to[i*prime[j]]=prime[j];
if(i%prime[j]==0)break;
}
}
for(;Q--;printf("%d\n",len)){
scanf("%d%d",&x,&y);len=y-x+1;
for(i=len;i>1;){
for(z=to[i];len%z==0&&ck(x,y-len/z,x+len/z,y);len/=z);
for(;i%z==0;i/=z);
}
}
}
T9 Fibonacci Representation 一开始写了个暴力set T了，然后加了个map+lower_bound才A。。
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;typedef long long LL;
int i,Q;
LL x,f[99];map<LL,int>F;
int find(LL n){
if(F[n])return F[n];
int b=lower_bound(f,f+91,n)-f;
if(f[b]==n)return 1;
return F[n]=min(find(n-f[b-1]),find(f[b]-n))+1;
}
int main(){
f[1]=1;f[2]=2;for(i=3;i<=91;i++)f[i]=f[i-1]+f[i-2];
for(scanf("%d",&Q);Q--;)scanf("%lld",&x),printf("%d\n",find(x));
}
T10 Squarks 首先最小的数一定是$x[1]+x[2]$，次小的数一定是$x[1]+x[3]$，而$x[2]+x[3]$可能是第$3~n$小的数，枚举$x[2]+x[3]$的位置，然后解方程得到$x[1]$、$x[2]$和$x[3]$，然后剩下的数最小的一定是$x[1]+x[4]$，由于$x[1]$已知，于是$x[4]$可知，然后判断$x[2]+x[4]$、$x[3]+x[4]$是否出现并删除，然后$x[5]...x[n]$以此类推，最后再判断一下是否是顺序上升的就可以了，时间复杂度$O(n^3)$
#include<cstdio>
#include<set>
#include<algorithm>
#define N 310
using namespace std;
int n,m,i,j,tot,a[N*N],x[N],ans[N][N];
multiset<int>w,s;
void ck(int a3){
if(a[1]+a[2]+a3&1)return;int i,j;s=w;
x[1]=a[1]+a[2]-a3>>1;x[2]=a[1]+a3-a[2]>>1;x[3]=a[2]+a3-a[1]>>1;
s.erase(s.find(a[1]));s.erase(s.find(a[2]));s.erase(s.find(a3));
for(i=4;i<=n;i++){
x[i]=*s.begin()-x[1];
if(x[i]<0)return;
for(j=1;j<i;s.erase(s.find(x[j]+x[i])),j++)if(s.find(x[j]+x[i])==s.end())return;
}
for(i=1;i<n;i++)if(x[i]>=x[i+1])return;
for(tot++,i=1;i<=n;i++)ans[tot][i]=x[i];
}
int main(){
for(scanf("%d",&n),m=n*(n-1)/2,i=1;i<=m;i++)scanf("%d",&a[i]),w.insert(a[i]);sort(a+1,a+m+1);
for(i=3;i<=n;i++)if(i==3||a[i]!=a[i-1])ck(a[i]);
for(printf("%d\n",tot),i=1;i<=tot;puts(""),i++)for(j=1;j<=n;j++)printf("%d ",ans[i][j]);
}
T11 Bidding 面向数据编程
#include<cstdio>
int main(){printf("756396726\n1");}
T12 Salaries 算出每个点的取值范围，从小到大扫描，如果当前$max i=k$只有一个点且在$1~k$中只有这一个数可用则这个点值确定，如果$maxi=k$的节点数=$1~k$中可用节点数把这些节点全部删去，标记为不可用
#include<cstdio>
#define N 1001000
int n,i,h,t,tot,res,rt,S,fir[N],ne[N],la[N],p[N],z[N],fa[N],s[N],sm[N],q[N],ans[N];bool v[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=n;i++){
scanf("%d%d",&p[i],&z[i]);
if(z[i])v[z[i]]=1,ans[i]=z[i],fa[z[i]]=z[i]-1;
if(p[i]!=i)ins(p[i],i);else p[rt=i]=0;
}
for(z[0]=n+1,q[h=t=1]=rt;h<=t;h++){
if(!z[q[h]])z[q[h]]=gf(z[p[q[h]]]-1),s[z[q[h]]]=q[h],sm[z[q[h]]]++;
for(i=fir[q[h]];i;i=ne[i])q[++t]=la[i];
}
for(i=1;i<=n;i++){
if(!v[i])S=i,res++;
if(sm[i]&&res==1)ans[s[i]]=S;
if(sm[i])res-=sm[i],S=0;
}
for(i=1;i<=n;i++)printf("%d\n",ans[i]);
}
T13 Leveling Ground 用前缀和使其变成单点修改，可以求出$ax+by=c$使得代价最小，先让$x$为正,$y$为负，然后$x$不断减$b$，$y$加$a$，通过堆得到一个最优的答案。真的好神啊~
#include<cstdio>
#include<algorithm>
#define N 100100
using namespace std;typedef long long LL;
int n,i,rt,s[N][2];
LL a,b,t,x,y,la,ans,tot,c[N],p[N],q[N],v[N];
LL exgcd(LL a,LL b,LL&x,LL&y){
if(!b){x=1;y=0;return a;}
LL t=exgcd(b,a%b,y,x);y-=x*(a/b);
return t;
}
LL get(int x){
LL now=0;
if(p[x]>0)now+=p[x];if(q[x]>0)now+=q[x];
if(q[x]+a>0)now-=q[x]+a;return now;
}
int mg(int x,int y){
if(!x||!y)return x+y;
if(v[x]<v[y])swap(x,y);
s[x][1]=mg(s[x][1],y);
swap(s[x][0],s[x][1]);
return x;
}
int main(){
scanf("%d%lld%lld",&n,&a,&b);if(b<a)swap(a,b);
t=exgcd(a,b,x,y);a/=t;b/=t;x=(x+b)%b;
for(i=1;i<=n;i++)scanf("%lld",&y),c[i]=la-y,la=y;
for(i=1,c[++n]=la;i<=n;i++){
if(c[i]%t)return puts("-1"),0;c[i]/=t;
p[i]=(c[i]*x)%b;if(p[i]<0)p[i]+=b;
q[i]=(c[i]-p[i]*a)/b;tot+=p[i];
v[i]=get(i);
rt=mg(rt,i);
}
for(tot/=b;tot--;){
x=rt;rt=mg(s[rt][0],s[rt][1]);s[x][0]=s[x][1]=0;
p[x]-=b;q[x]+=a;v[x]=get(x);
rt=mg(rt,x);
}
for(i=1;i<=n;i++){if(p[i]>0)ans+=p[i];if(q[i]>0)ans+=q[i];}
printf("%lld",ans);
}
T14 Minimalist Security 对于每一个连通块，对一个点设未知数$x$，则剩下的点都可以用$x$表示，如果碰到两边都已经表示过，如果不同号则判一下常数是否合法，否则则可以算出$x$的值，如果$x$的值有多个则不合法，顺便可以根据$0\leq x+w[i]\leq p[i]$算出$x$的$[l,r]$取值范围，然后就可以得到答案了
#include<cstdio>
#include<algorithm>
#define N 500500
#define M 6006000
using namespace std;
int n,m,i,x,y,z,h,t,u,tot,ans,l,r,sz,s,fir[N],la[M],va[M],ne[M],v[N],w[N],p[N],q[N];
long long sum,now,lv,rv;bool flag;
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
int main(){
for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&p[i]),sum+=p[i];
for(;m--;)scanf("%d%d%d",&x,&y,&z),ins(x,y,z),ins(y,x,z);
for(s=1;s<=n;s++)if(!v[s]){
for(q[t=1]=s,v[s]=1,ans=-1,h=sz=0,now=0,l=0,r=p[s];h^t;){
if(v[u=q[++h]]<2)sz++,now+=w[u],l=max(l,-w[u]),r=min(r,p[u]-w[u]);
else sz--,now+=w[u],l=max(l,w[u]-p[u]),r=min(r,w[u]);
for(i=fir[u];i;i=ne[i]){
y=la[i];z=va[i]-w[u];
if(v[y]){
if(3-v[u]==v[y]){if(z!=w[y])return puts("NIE"),0;}else{
x=w[y]-z;if(x&1)return puts("NIE"),0;
x>>=1;if(v[y]<2)x=-x;
if(ans<0||ans==x)ans=x;else return puts("NIE"),0;
}
}else v[y]=3-v[u],w[y]=z,q[++t]=y;
}
}
if(l>r)return puts("NIE"),0;
if(ans>0){
if(ans<l||ans>r)return puts("NIE"),0;
l=r=ans;
}
if(sz>0)lv+=1ll*r*sz+now,rv+=1ll*l*sz+now;else lv+=1ll*l*sz+now,rv+=1ll*r*sz+now;
}
printf("%lld %lld",sum-lv,sum-rv);
}
T15 Warehouse Store 一开始写线段树乱搞但发现是不对的，应该要用贪心的思想，每次能加就加，不能加就在已经加的中找最大的换，这样就能保证正确性
#include<cstdio>
#include<map>
#include<queue>
#define mp make_pair
#define N 252000
using namespace std;
priority_queue<pair<int,int> >q;
int n,i,x,va,id,cnt,a[N];bool w[N];long long now;
int main(){
for(scanf("%d",&n),i=1;i<=n;i++)scanf("%d",&a[i]);
for(i=1;i<=n;i++){
scanf("%d",&x);now+=a[i];
if(now>=(long long)x)now-=x,q.push(mp(x,i)),w[i]=1;else
if(!q.empty()){
va=q.top().first;id=q.top().second;
if(va>x)q.pop(),w[id]=0,now+=va-x,q.push(mp(x,i)),w[i]=1;
}
}for(i=1;i<=n;i++)if(w[i])cnt++;
for(printf("%d\n",cnt),i=1;i<=n;i++)if(w[i])printf("%d\n",i);
}
T16 Prefixuffix 用$f_i$表示串$[i+1,n-i]$中最长的串使$[i+1,i+f_i]=[n-i-f_i+1,n-i]$,这时有一个性质$f_{i-1}\leq f_i+2$，然后就可以线性递推
不过这题unsigned long long自然溢出会挂，于是只能取模，不过这题其实$O(nlgn)$暴力也能过的、YY大爷%%%
#include<cstdio>
#include<cstring>
#include<algorithm>
#define S 1000000003
#define M 1000000009
#define N 1001000
using namespace std;typedef long long LL;
int n,i,j,ans;char s[N];LL pw[N],sum[N];
LL get(int l,int r){return (sum[r]+M-sum[l-1]*pw[r-l+1]%M)%M;}
int main(){
for(scanf("%d%s",&n,s+1),pw[0]=i=1;i<=n;i++)pw[i]=pw[i-1]*S%M,sum[i]=(sum[i-1]*S%M+s[i])%M;
for(i=n>>1;~i;i--)
for(j=min(n/2-i,j+2);j>=0;j--)if(get(i+1,i+j)==get(n-i-j+1,n-i)){
if(get(1,i)==get(n-i+1,n))ans=max(ans,i+j);
break;
}
printf("%d",ans);
}
T17 Tour de Byteotia 把大于$k$的先加入并查集，然后剩余的判是否构成环就可以了，写了个按秩合并的T了，按秩合并+路径压缩也T了，改成路径压缩才A。。
#include<cstdio>
#define N 1001000
int n,m,k,i,p,q,ans,a[N*2],b[N*2],fa[N];char ch;
int gf(int x){return fa[x]==x?x:fa[x]=gf(fa[x]);}
void read(int &x){
for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
int main(){
for(read(n),read(m),read(k),i=1;i<=n;i++)fa[i]=i;
for(i=1;i<=m;i++){
read(a[i]);read(b[i]);
if(a[i]>k&&b[i]>k)p=gf(a[i]),q=gf(b[i]),fa[p]=q;
}
for(i=1;i<=m;i++)if(a[i]<=k||b[i]<=k){
p=gf(a[i]);q=gf(b[i]);
if(p==q)ans++;else fa[p]=q;
}
printf("%d",ans);
}
评论 (0)
