题解

23 条题解

  • 0
    @ 2014-11-06 00:03:22

    测试数据 #0: Accepted, time = 15 ms, mem = 20008 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 20012 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 20012 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 20012 KiB, score = 10
    测试数据 #4: Accepted, time = 15 ms, mem = 20008 KiB, score = 10
    测试数据 #5: Accepted, time = 46 ms, mem = 20012 KiB, score = 10
    测试数据 #6: Accepted, time = 250 ms, mem = 20016 KiB, score = 20
    测试数据 #7: Accepted, time = 859 ms, mem = 20016 KiB, score = 20
    Accepted, time = 1200 ms, mem = 20016 KiB, score = 100
    这个题输出及其麻烦 真是蛋疼
    void MinCostMaxFlow()
    {
    int nannan;
    int lovenannan=0;
    while(Spfa())Adjust();
    ans=exp(-ans);
    while(ans<0.99999999999999999)ans=ans*10,lovenannan++;
    if(lovenannan>0)
    {
    printf("0.");
    for(int i=1;i<lovenannan-1;i++)printf("0");
    ans=ans*10000;
    nannan=(int)ans;
    if(ans-nannan>0.5)nannan++;
    if(nannan<100000)
    {
    if(lovenannan!=1)printf("0");
    printf("%d",nannan);
    }
    else printf("%d",nannan/10);
    }
    else printf("1.0000");
    }

  • 0
    @ 2014-08-18 11:24:17

    算了,将就一下吧

  • 0
    @ 2014-08-18 11:23:56

    为什么会这样。。。

  • 0
    @ 2014-08-18 11:23:45

    。。。

  • 0
    @ 2014-08-18 11:23:34

    贴个程序晾凉。。。
    type ss=record
    x,y,c,r,next:longint;
    f:extended;
    end;
    const maxn=401; maxm=46001; qu=10000; oo=maxlongint shr 2;
    var i,j,n,cnt,st,ed,w,tot,t1,t2,t4,k,t,h,flow,augo,hh,tt:longint;
    pr:string;
    s,x:array[0..maxn] of extended;
    y,pre,b:array[0..maxn] of longint;
    f:array[0..maxn] of boolean;
    e:array[0..maxm] of ss;
    q:array[0..qu] of longint;
    ans,t3,cost:extended;
    procedure jia(x,y,c:longint;f:extended);
    begin
    inc(tot); e[tot].x:=x; e[tot].y:=y; e[tot].c:=c; e[tot].f:=f;
    e[tot].next:=b[x]; b[x]:=tot;
    inc(tot); e[tot].x:=y; e[tot].y:=x; e[tot].f:=-f;
    e[tot].next:=b[y]; b[y]:=tot;
    e[tot].r:=tot-1; e[tot-1].r:=tot;
    end;
    begin
    readln(n,k);
    for i:=1 to n do read(x[i]);
    for i:=1 to n do read(y[i]);
    st:=n+1; ed:=n+2; cnt:=n+3; fillchar(b,sizeof(b),255);
    jia(st,cnt,k,0);
    for i:=1 to n do
    if y[i]>0 then jia(cnt,i,y[i],-ln(x[i]));
    for i:=1 to n do
    begin
    read(t);
    if t=1 then jia(i,ed,oo,0);
    end;
    while true do
    begin
    read(t1,t2);
    if t1=-1 then break;
    readln(t3,t4);
    jia(t1,t2,t4,-ln(t3));
    jia(t2,t1,t4,-ln(t3));
    end;
    ans:=1;
    while true do
    begin
    for i:=1 to cnt do s[i]:=oo;
    h:=1; t:=1; q[1]:=st; s[st]:=0; hh:=1; tt:=1;
    repeat
    w:=q[h]; f[w]:=false; i:=b[w];
    inc(h); inc(hh); h:=h mod qu;
    while i<>-1 do
    begin
    if (s[e[i].y]-s[w]-e[i].f>1e-12) and (e[i].c>0) then
    begin
    s[e[i].y]:=s[w]+e[i].f;
    pre[e[i].y]:=i;
    if not(f[e[i].y]) then
    if s[e[i].y]<s[q[h]] then
    begin
    dec(h); dec(hh);
    if h<0 then h:=qu-1;
    q[h]:=e[i].y;
    end
    else
    begin
    inc(t); inc(tt);
    t:=t mod qu;
    q[t]:=e[i].y;
    end;
    f[e[i].y]:=true;
    end;
    i:=e[i].next;
    end;
    until hh>tt;
    if s[ed]=oo then break;
    flow:=maxlongint;
    i:=pre[ed];
    while i<>0 do
    begin
    if flow>e[i].c then flow:=e[i].c;
    i:=pre[e[i].x];
    end;
    i:=pre[ed]; cost:=0;
    while i<>0 do
    begin
    cost:=e[i].f+cost; dec(e[i].c,flow);
    inc(e[e[i].r].c,flow); i:=pre[e[i].x];
    end;
    for i:=1 to flow do ans:=ans*exp(-cost);
    inc(augo,flow);
    end;
    if augo<k then writeln(0) else
    begin
    write('0.'); ans:=ans*10;
    while ans<1 do
    begin
    ans:=ans*10;
    write(0);
    end;
    for i:=1 to 10 do ans:=ans*10;
    for i:=1 to 6 do ans:=round(ans/10);
    writeln(trunc(ans));
    end;
    end.

  • 0
    @ 2014-05-26 22:04:17

    http://hi.baidu.com/macaulish64/item/7d8a97f72961eb37a729885a
    如果你只过了前5个点,那个恭喜你,程序应该是没有错的,错的是浮点运算还是什么balabala的,就是精度问题,解决方法去看我空间吧!

  • 0
    @ 2013-06-06 22:30:27

    稍微对反向弧的费用处理一下 取倒数是不要四舍五入 而是 退一 要不有可能出现负权环
    挺慢的代码 不过算是A了
    VijosEx via JudgeDaemon2/13.6.5.0 via libjudge
    编译成功

    测试数据 #0: Accepted, time = 0 ms, mem = 1456 KiB, score = 10
    测试数据 #1: Accepted, time = 0 ms, mem = 1456 KiB, score = 10
    测试数据 #2: Accepted, time = 0 ms, mem = 1456 KiB, score = 10
    测试数据 #3: Accepted, time = 15 ms, mem = 1504 KiB, score = 10
    测试数据 #4: Accepted, time = 0 ms, mem = 1508 KiB, score = 10
    测试数据 #5: Accepted, time = 3 ms, mem = 1620 KiB, score = 10
    测试数据 #6: Accepted, time = 46 ms, mem = 1828 KiB, score = 20
    测试数据 #7: Accepted, time = 140 ms, mem = 2464 KiB, score = 20
    Accepted, time = 204 ms, mem = 2464 KiB, score = 100
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #include <cstdio>
    #include <vector>

    using namespace std;

    #define MAXN 500

    const double detail=0.999999999999;

    int n,k;

    double as[MAXN];
    int am[MAXN];

    struct node {
    int t,v;
    double c;
    node *next,*next0;
    };

    node *map[MAXN][MAXN];
    node *head[MAXN];

    int Insert(int s,int t,int f,double c){
    if (map[s][t]==NULL){
    node *p=new(node);
    (*p).t=t;
    (*p).c=c;
    (*p).v=f;
    (*p).next0=NULL;
    (*p).next=head[s];
    head[s]=p;
    map[s][t]=p;
    } else {
    node *p=map[s][t];
    while (p!=NULL){
    if ((*p).c==c){
    (*p).v+=f;
    return 0;
    }
    p=(*p).next0;
    }
    p=new(node);
    (*p).t=t;
    (*p).v=f;
    (*p).c=c;
    (*p).next=head[s];
    head[s]=p;
    (*p).next0=map[s][t];
    map[s][t]=p;
    }
    return 0;
    }

    double dist[MAXN],minc[MAXN];
    int suff[MAXN],minf[MAXN];
    bool f[MAXN];
    int max_flow=0;

    struct cmp{
    bool operator()(int x, int y){
    return dist[x]<dist[y];
    }
    };

    priority_queue<int,vector<int>,cmp>qu;

    double EXP(double x,int y){
    if (y==1) return x;
    return EXP(x,y/2)*EXP(x,y-(y/2));
    }

    double minimum_cost_flow(int s,int t){
    double rec=1;
    while (1){
    memset(dist,0,sizeof(dist));
    memset(f,false,sizeof(f));
    f[s]=true;
    dist[s]=1;
    suff[s]=0;
    minf[s]=0x7fffffff;
    qu.push(s);
    while (!qu.empty()){
    int u=qu.top();
    qu.pop();
    if (f[u]){
    f[u]=false;
    node *p=head[u];
    while (p!=NULL){
    if ((p).v>0&&dist[u](*p).c>dist[(*p).t]){
    dist[(p).t]=dist[u](*p).c;
    suff[(*p).t]=u;
    f[(*p).t]=true;
    qu.push((*p).t);
    minf[(*p).t]=min(minf[u],(*p).v);
    minc[(*p).t]=(*p).c;
    }
    p=(p).next;
    }
    }
    }
    if (dist[t]){
    max_flow+=minf[t];
    int i=t;
    while (suff[i]){
    rec
    =EXP(minc[i],minf[t]);
    Insert(suff[i],i,-minf[t],minc[i]);
    Insert(i,suff[i],minf[t],double(1)/double(minc[i])*detail);
    i=suff[i];
    }
    } else break;
    }
    return rec;
    }

    void output_double(double x,int y){
    int i=0,l=0;
    int ans[15];
    ans[0]=0;
    while (1){
    x*=10;
    int z=int(x);
    x-=int(x);
    ans[++l]=z;
    if (z||i) i++;
    if (i>=y+1) break;
    }
    if (ans[l]>=5) ans[l-1]++;
    int j=l-1;
    while (ans[j]>=10) {
    ans[j-1]+=ans[j]/10;
    ans[j]%=10;
    j--;
    }
    printf("%d.",ans[0]);
    for (int i=0;i++<l-1;) printf("%d",ans[i]);
    printf("\n");
    }

    int main(){
    scanf("%d%d",&n,&k);
    for (int i=0;i<MAXN;i++){
    head[i]=NULL;
    for (int j=0;j<MAXN;j++){
    map[i][j]=NULL;
    }
    }
    for (int i=0;i++<n;) {
    scanf("%lf",&as[i]);
    }
    for (int i=0;i++<n;) {
    scanf("%d",&am[i]);
    if (am[i]){
    Insert(n+1,i,am[i],as[i]);
    }
    }
    for (int i=0;i++<n;){
    int x;
    scanf("%d",&x);
    if (x){
    Insert(i,n+2,0x7fffffff,1);
    }
    }
    while (1){
    int x,y,m;
    double s;
    scanf("%d%d",&x,&y);
    if (x==-1&&y==-1) break;
    scanf("%lf%d",&s,&m);
    Insert(x,y,m,s);
    Insert(y,x,m,s);
    }
    Insert(n+3,n+1,k,1);
    double ans=minimum_cost_flow(n+3,n+2);
    if (max_flow<k) printf("0\n");
    else output_double(ans,5);
    return 0;
    }

  • 0
    @ 2010-07-22 13:37:47

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:运行超时...

    ├ 测试数据 07:运行超时...

    ├ 测试数据 08:运行超时...

    ---|---|---|---|---|---|---|---|-

    Unaccepted 有效得分:50 有效耗时:0ms

    为啥??? 精度造成的负环???

  • 0
    @ 2010-07-13 19:06:58

    楼上误了,不是牛,是鱼。。。。

  • 0
    @ 2010-04-04 10:42:51

    注意 浮点运算 精度 问题

    可能会导致 出现 负圈……

    多亏牛人提醒,否则这题 本菜 是 A不了 的。。。

  • 0
    @ 2009-11-04 22:22:30

    米有什么人做?找找感觉吧

  • 0
    @ 2009-09-12 16:09:39

    我做有关实数的题比较少

    所以饱受精度的煎熬!!!

  • 0
    @ 2009-08-24 19:04:11

    一直90,一直以为是Pascal的精度问题,后来发现写zkw费用流时标号部分少写一句话,囧...

    Accepted 有效得分:100 有效耗时:0ms

  • 0
    @ 2009-08-18 19:58:49

    spfaMS可以啊。。就是慢点。。

    编译通过...

    ├ 测试数据 01:答案正确... 0ms

    ├ 测试数据 02:答案正确... 0ms

    ├ 测试数据 03:答案正确... 0ms

    ├ 测试数据 04:答案正确... 0ms

    ├ 测试数据 05:答案正确... 0ms

    ├ 测试数据 06:答案正确... 0ms

    ├ 测试数据 07:答案正确... 0ms

    ├ 测试数据 08:答案正确... 368ms

    ---|---|---|---|---|---|---|---|-

    Accepted 有效得分:100 有效耗时:368ms

  • 0
    @ 2009-08-18 12:22:32

    这题的输出真萎缩啊……

    还有SPFA直接挂,改成zkw费用流就AC了……

    • @ 2013-06-06 22:31:36

      表示SPFA很慢的过了。。。。

  • 0
    @ 2009-08-17 15:06:22

    算法艺术与信息学竞赛里面有

    我上午还看到的呢

  • 0
    @ 2009-08-22 13:13:15

    裸的费用流......

  • 0
    @ 2009-08-16 11:59:37

    黑书是么?

    那个《算法导论》还是刘汝佳写的《算法艺术》?

  • 0
    @ 2009-08-15 17:50:01

    取对数最小费用

  • 0
    @ 2009-08-15 16:52:19

    神题……

    最小费用流……

信息

ID
1621
难度
7
分类
图结构 | 网络流 点击显示
标签
递交数
261
已通过
54
通过率
21%
上传者