WA60求助
查看原帖
WA60求助
556362
Unnamed114514楼主2023/7/20 17:11
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e3+5,M=1e5+5;
int l,r,s,t,tot,ans1,ans2,a[N],dis[N],head[N],nxt[M],to[M],c[M],delta,cost[M],ans,in[N],out[N];
bool vis[N];
inline void add_edge(int u,int v,int w,int C){
	++tot,nxt[tot]=head[u],head[u]=tot,to[tot]=v,c[tot]=w,cost[tot]=C;
}
queue<int> q;
inline bool SPFA(int s){
	memset(dis,inf,sizeof(dis));
	memset(vis,0,sizeof(vis));
	while(q.size()) q.pop();
	q.push(s),dis[s]=0,vis[s]=1;
	while(q.size()){
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int H=head[u];~H;H=nxt[H]){
			int v=to[H],w=c[H],C=cost[H];
			if(w&&dis[u]+C<dis[v]){
				dis[v]=dis[u]+C;
				if(!vis[v]){
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	if(dis[t]==inf)
		return 0;
	else
		return 1;
}
int dfs(int u,int F){
	if(u==t)
		return F;
	vis[u]=1;
	int rest=F;
	for(int H=head[u];~H;H=nxt[H]){
		int v=to[H],w=c[H],C=cost[H];
		if(!vis[v]&&w>0&&dis[v]==dis[u]+C){
			int Delta=dfs(v,min(w,rest));
			if(!Delta)
				dis[v]=inf;
			ans2-=Delta*C;
			c[H]-=Delta,c[H^1]+=Delta;
			rest-=Delta;
		}
	}
	vis[u]=0;
	return F-rest;
}
inline void dinic(){
	while(SPFA(s))
		ans1+=dfs(s,inf);
}
inline bool check(int x,int y){
	int t=x*x-y*y,z=sqrt(t);
	if(z*z!=t)
		return 0;
	if(__gcd(y,z)==1)
		return 1;
	return 0;
}
inline void add(int u,int v,int w,int C){
	add_edge(u,v,w,C),add_edge(v,u,0,-C);
}
int main(){
	memset(head,-1,sizeof(head)),tot=1;
	scanf("%d%d",&l,&r);
	s=0,t=(r-l+1)*2+2;
	for(int i=l;i<=r;++i){
		in[i]=(i-l+1)*2-1,out[i]=(i-l+1)*2;
		add(in[i],out[i],1,0);
		for(int j=l;j<i;++j)
			if(check(i,j)){
				add(s,in[i],1,0);
				add(out[j],t,1,0);	 
				add(out[i],in[j],1,-j-i);
			}
	}
	dinic();
	printf("%d %d\n",ans1,ans2);
	return 0;
}
2023/7/20 17:11
加载中...