QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#810716#130. Cost Performance Flowcdx123456WA 1ms3612kbC++142.0kb2024-12-12 09:38:542024-12-12 09:39:01

Judging History

你现在查看的是最新测评结果

  • [2024-12-12 09:39:01]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3612kb
  • [2024-12-12 09:38:54]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define int long long
int cnt=-1,ans,anss,n,m,s,t,T,d[110],f[110],head[110],pre[110],inf=1e9;
bool qi[110];
struct ee{
	int next,to,dis,w;
}e[3010];
struct fs{
	int fz,fm;
};
int gcd(int x,int y){
	if(!y) return x;
	return gcd(y,x%y);
}
bool operator < (fs x,fs y){
	return x.fz*y.fm<y.fz*x.fm;
}
void add(int x,int y,int ff,int w){
	e[++cnt].to=y;
	e[cnt].next=head[x];
	e[cnt].dis=ff;
	e[cnt].w=w;
	head[x]=cnt;
}
bool spfa(){
	queue<int> q; 
	memset(d,0x3f,sizeof(d));
	memset(f,0,sizeof(f));
	f[s]=inf;
	d[s]=0;
	qi[s]=1;
	q.push(s);
	while(!q.empty()){
		int x=q.front(); q.pop(); qi[x]=0;
		for(int i=head[x];i!=-1;i=e[i].next){
			if(e[i].dis && d[e[i].to]>d[x]+e[i].w){
				d[e[i].to]=d[x]+e[i].w;    f[e[i].to]=min(f[x],e[i].dis);    pre[e[i].to]=i;
				if(qi[e[i].to]) continue;
				qi[e[i].to]=1;; q.push(e[i].to);
			}
		}
	}
	return f[t]>0;
}
void ek(){
	while(spfa()){
		ans+=f[t]*d[t];
		anss+=f[t];
		for(int i=t;i!=s;i=e[pre[i]^1].to){
			e[pre[i]].dis-=f[t]; e[pre[i]^1].dis+=f[t]; 
		}
	}
}
signed main(){
	int x,y,z,w;
	memset(head,-1,sizeof(head));
	cin>>n>>m>>s>>T;
	t=n+1;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z>>w;
		add(x,y,z,w);
		add(y,x,0,-w);
	}
	add(T,t,inf,0);
	add(t,T,0,0);
	ek();
	for(int i=0;i<=cnt;i+=2) e[i].dis+=e[i^1].dis,e[i^1].dis=0;
	e[cnt-1].dis-=inf;
	ans=0;
	
	int M=anss,lans=0;
	fs minn;
	for(int i=0;i<M;i++){
		e[cnt-1].dis++;
		ek();
		w=ans-lans;
		fs k;
		if(2*(M-i)-lans*w*2<=0){
			k.fz=lans*lans+(M-i)*(M-i);
			k.fm=1;
		}else if(2*(M-i)-lans*w*2>=2*w*w+2){
			k.fz=lans*lans+w*w+(lans*w*2-2*(M-i))+(M-i)*(M-i)+1;
			k.fm=1;
		}else{
			k.fz=2*(M-i)-lans*w*2;
			k.fm=2*w*w+2;
			k.fz=(k.fz*k.fz*(w*w+1)+k.fz*k.fm*(lans*w*2-2*(M-i))+k.fm*k.fm*(lans*lans+w*w));
			k.fm*=k.fm;
		}
		x=gcd(k.fz,k.fm);
		k.fz/=x;
		k.fm/=x;
		if(i==0 || k<minn) minn=k;
		lans=ans;
	}
	cout<<minn.fz<<'/'<<minn.fm<<endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3612kb

input:

10 90
9 7
1 5 3 3
7 5 1 65
7 9 83 3
10 3 1 29
7 1 1 25
8 2 1 1
3 9 1 6
2 10 39 81
2 8 29 1
6 8 68 81
9 8 7 28
10 6 99 2
7 4 1 13
3 2 2 27
6 5 1 28
3 1 4 40
9 4 42 2
5 10 1 71
1 6 2 5
9 10 44 5
3 10 21 12
8 1 1 26
8 4 44 11
3 5 4 22
2 3 35 1
9 3 10 12
4 1 10 30
2 7 38 14
5 3 59 11
5 9 91 26
8 7 48 50...

output:

14384/13

result:

wrong answer 1st lines differ - expected: '430592/13', found: '14384/13'