QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#810716 | #130. Cost Performance Flow | cdx123456 | WA | 1ms | 3612kb | C++14 | 2.0kb | 2024-12-12 09:38:54 | 2024-12-12 09:39:01 |
Judging History
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;
}
詳細信息
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'