首页 > 代码库 > 5.6水题合集

5.6水题合集

T1:杭州旅行

floyd 求最小环,相当于枚举环上编号最大的点进行转移

正确性:

一个环中的最大结点为k(编号最大),与他相连的两个点为i,j,这个环的最短长度为g[i][k]+g[k][j]+i到j的路径中,所有结点编号都小于k的最短路径长度
根据floyd的原理,在最外层循环做了k-1次之后,dist[i][j]则代表了i到j的路径中,所有结点编号都小于k的最短路径
综上所述,该算法一定能找到图中最小环

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define RG register
using namespace std;
const int N=850;
const int Inf=19260817;
int gi(){
	int x=0;
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) ch=getchar();
	while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
	return x;
}
int f[N][N],w[N][N],n,m;
int main(){
    freopen("zdlcs.in","r",stdin);
    freopen("zdlcs.out","w",stdout);
    n=gi(),m=gi();
    for(RG int i=1;i<=n;i++){
	for(RG int j=1;j<=n;j++){
	    if(i!=j) f[i][j]=w[i][j]=Inf;
	}
    }
    for(int i=1;i<=m;i++){
	int x=gi(),y=gi(),z=gi();
	w[x][y]=min(w[x][y],z);
	w[y][x]=f[y][x]=f[x][y]=w[x][y];
    }
    int ans=Inf;
    for(RG int k=1;k<=n;k++){
	for(RG int i=1;i<k;i++)
	    for(RG int j=1;j<i;j++){
		ans=min(ans,f[i][j]+w[k][i]+w[k][j]);
	    }
	for(RG int i=1;i<=n;i++){
	    for(RG int j=1;j<=n;j++){
		if(k!=i&&k!=j) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	    }
	}
    }
    if(ans==Inf) puts("It‘s impossible.");
    else printf("%d\n",ans);
}

 T2:奇偶性游戏

跟狡猾的商人一模一样,多了一个离散化,把+变成异或即可

做法:如果知道[L,R],[L,r],那么[r-1,R]的奇偶就可以确定后,所以只要动态维护合并每个连通块中点到根的距离

如果已经在同一个连通块中就可以直接判断

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#define RG register
using namespace std;
const int N=100000;
struct data {
  int l,r,c;
} q[N];
int fa[N],sum[N],hsh[N],n,Q,tot;
char s[10];
int gi(){
	int x=0;
	char ch=getchar();
	while(ch<‘0‘||ch>‘9‘) ch=getchar();
	while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
	return x;
}
inline int find(RG int x) {
	if (fa[x]==x) return x;
	RG int u=find(fa[x]);
	sum[x]^=sum[fa[x]];
	return fa[x]=u;
}
inline void work() {
	n=gi(),Q=gi();
	for (RG int i=1; i<=Q; ++i) {
		q[i].l=gi()-1,q[i].r=gi();
		hsh[++tot]=q[i].l,hsh[++tot]=q[i].r;
		scanf("%s",s),q[i].c=s[0]==‘o‘;
	}
	sort(hsh+1,hsh+tot+1),tot=unique(hsh+1,hsh+tot+1)-hsh-1;
	for (RG int i=1;i<=tot;i++) fa[i]=i;
	for (RG int i=1;i<=Q;i++) {
		q[i].l=lower_bound(hsh+1,hsh+tot+1,q[i].l)-hsh;
		q[i].r=lower_bound(hsh+1,hsh+tot+1,q[i].r)-hsh;
		RG int x=find(q[i].l),y=find(q[i].r);
		if (x==y && (sum[q[i].l]^sum[q[i].r])!=q[i].c) {
			printf("%d\n",i-1);
			return;
		}
		if (x>y) swap(x,y);
		fa[y]=x,sum[y]=sum[q[i].l]^sum[q[i].r]^q[i].c;
	}
	printf("%d\n",Q);
	return;
}
int main() {
	freopen("parity.in","r",stdin);
	freopen("parity.out","w",stdout);
	work();
	return 0;
}

 T3:膜拜神犇

考虑这种有向图求环之类的问题考虑tarjan;

缩完点后原图变为一个DAG,考虑缩完点后的图中的点的情况只有三种:

1.1号节点所在的强连通分量可以到达,称之为一类

2.能到达1号节点所在的强连通分量,称之为二类

3.跟1号节点所在的强连通分量没啥关系

 

第三中可以省略;考虑答案的构成,

必定由1号点所在的强连通分量走到一个一类点,再选一个与这个一类点相连的二类点,把它们之间的这条边选择反向走.

(这条边本来必然是由二类点指向一类点的,否则,1号结点所在的强连通分量必然可以到达这个二类点,

而二类点由是可以到达1号点所在的强连通分量的,这样就有环了,而DAG是无环图)

然后再从这个二类点走到一号点所在的强连通分量.

于是我们只需要求出

1.1号节点所在的强连通分量到每个一类点的MAX_dis;

2.每个二类点到1号节点所在的强连通分量的MAX_dis(这个实现的话把边全部反过来,变为求1到它们的距离)

然后把他们组合起来再减去1号节点所在的强连通分量的大小

DAG的最大权值路径可直接spfa;

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#define RG register
using namespace std;
const int N=100010;
const int Inf=19260817;
int tt,tim,cnt,tp;
bool w[N];
int head[N],to[N],nxt[N],dfn[N],low[N],zhan[N],fr[N],size[N],n,m;
int dis[N][3],q[N*20];
vector<int>p[N][3];
inline int gi() {
    int x=0;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘) ch=getchar();
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x;
}
inline void dfs(int x) {
    dfn[x]=low[x]=++tim;
    zhan[++tp]=x,w[x]=1;
    for(RG int i=head[x];i;i=nxt[i]) {
	int y=to[i];
	if(!dfn[y]) {
	    dfs(y);low[x]=min(low[x],low[y]);
	} else if(w[y]) low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x]) {
	int y;cnt++;
	do {
	    y=zhan[tp--];
	    w[y]=0,fr[y]=cnt,size[cnt]++;
	} while(y!=x);
    }
}
inline void spfa(int x){
    dis[fr[1]][x]=size[fr[1]];int t=0,sum=1;q[0]=fr[1];
    while(t<sum){
	int now=q[t++];
	for(RG int i=0;i<p[now][x].size();i++){
	    int y=p[now][x][i];
	    if(dis[y][x]<dis[now][x]+size[y]){
		dis[y][x]=dis[now][x]+size[y];
		q[sum++]=y;
	    }
	}
    }
}
int main() {
    freopen("OrzOrz.in","r",stdin);
    freopen("OrzOrz.out","w",stdout);
    n=gi(),m=gi();
    for(RG int i=1;i<=m;i++) {
	int x=gi(),y=gi();
	to[++tt]=y,nxt[tt]=head[x],head[x]=tt;
    }
    for(RG int i=1;i<=n;i++) if(!dfn[i]) dfs(i);
    for(RG int i=1;i<=n;i++)
	for(RG int j=head[i];j;j=nxt[j])
	    if(fr[to[j]]!=fr[i]){
		p[fr[i]][1].push_back(fr[to[j]]);
		p[fr[to[j]]][2].push_back(fr[i]);
	    }
    spfa(1);spfa(2);int ans=0;
    for(RG int i=1;i<=cnt;i++){
	for(RG int j=0;j<p[i][2].size();j++){
	    int y=p[i][2][j];
	    if(dis[i][1]!=0&&dis[y][2]!=0){
		ans=max(ans,dis[i][1]+dis[y][2]);
	    }
	}
    }
    printf("%d\n",ans-size[fr[1]]);
    return 0;
}

T4: PG图

最小值最大考虑二分;

对于每一条边:w[i]+sum[u]-sum[v]>=mid;

sum[v]-sum[u]<=w[i]-mid;与最短路的松弛操作相似,用差分约束check;

于是从v向u连一条w[i]-mid的边,判断是否有负权环即可.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1000,M=3000;
int head[N],to[M],nxt[M],s[M],c[M],dis[N],vis[N],n,m;
struct Data {
    int x,y,z;
} g[M];
int gi() {
    int x=0,flag=1;
    char ch=getchar();
    while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘){flag=-1;}ch=getchar();}
    while(ch>=‘0‘&&ch<=‘9‘) x=x*10+ch-‘0‘,ch=getchar();
    return x*flag;
}
bool spfa(int x) {
    for(int i=head[x];i;i=nxt[i]) {
	int y=to[i];
	if(dis[y]>dis[x]+s[i]) {
	    dis[y]=dis[x]+s[i];
	    if(vis[y]++>100||spfa(y)) return 1;
	}
    }
    return 0;
}
int main() {
    freopen("pg.in","r",stdin);
    freopen("pg.out","w",stdout);
    while(scanf("%d%d",&n,&m)!=EOF) {
	memset(head,0,sizeof(head));
	for(int i=1;i<=m;i++) {
	    int x=gi(),y=gi();c[i]=gi();
	    to[i]=y,nxt[i]=head[x],head[x]=i;
	}
	int l=0,r=10001;
	while(l<=r) {
	    int mid=(l+r)>>1;int flag=0;
	    for(int i=1;i<=m;i++) s[i]=c[i]-mid;
	    for(int i=1;i<=n;i++) {
		memset(dis,127,sizeof(dis));
		memset(vis,0,sizeof(vis));
		if(spfa(i)) {flag=1;break;};
	    }
	    if(flag) r=mid-1;
	    else l=mid+1;
	}
	if(r<0) puts("No Solution");
	else if(r==10001) puts("Infinite");
	else printf("%d\n",r);
    }
    return 0;
}

 

5.6水题合集