P3199

· · 个人记录

[HNOI2009]最小圈

然后 0/1 分数规划似乎有点诡异。。。

如果说 \sum_{i=1}^k (w_i-mid)\le 0 ，那么就会有 \dfrac{\sum_{i=1}^k w_i}{k}\le mid 。

然后二分什么的。。。

然后就是把边权修改后判负环即可。。。然后我写的 SPFA 判负环似乎有亿点点慢。。。最后莫名其妙有了 80pts 。最后又只有 20pts 。。。（是数据的锅还是我的锅。。。）后来事实证明出题人刻意卡了 SPFA 但是没有卡 dfs 版的 SPFA （精心构造结果被这样钻空子了。。。）。

然后想写正常的 SPFA 判负环可以作一些玄学优化，比如说把入队次数 \ge n 改为 \ge 25 之类的，反正把 n 调成一个合适的常数同样是可以过掉的。。。但反正没有正确性。。。或者从某种角度说这个 0/1 分数规划本身就是复杂度不对的做法。。。

关于一些负环的写法在我的博客 P3385 有说明，这里不再概括之类的。

正解似乎就是 Karp 1977年的论文上的结论。。。这里是 rqy 的翻译，以及他（她？）的拓展：The Minimum Cycle Mean in a Digraph 。

这里再写个大略。

求有向强联通图中最小平均权值回路。这里令 \lambda^* 为最小平均权值回路的平均权值，定义 F_k(v) 为从 s （起始点）到 v （某一点）恰好经过 k 条边的最短路（不存在则为 \infty） 。

那么有如下结论：

\lambda^*=\min_{v\in V}\max_{0\le k\le n-1}[\dfrac{F_n(v)-F_k(v)}{n-k}]

然后关于 F_k(v) 有一个递推式：

F_k(v)=\min_{(u,v)\in E,k\in [1,n]}[F_{k-1}(u)+w(u,v)]

初始条件为：

F_0(s)=0;F_0(v)=\infty,v\not=s

然后就是求答案了。

然后这个东西当结论记住大概也是蛮好。。。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll N=3e3,M=1e4,inf=1e12;

ll n,m;

ll u[M+5],v[M+5];

double ans=inf,tmp;

double f[N+5][N+5],w[M+5];

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u[i]=read();v[i]=read();scanf("%lf",&w[i]);
    //  add(u,v,w);
    }

    for(ll i=0;i<=n;i++) {
        for(ll j=1;j<=n;j++) {
            if(!i) f[i][j]=0;
            else f[i][j]=inf;
        }
    }

    for(ll k=1;k<=n;k++) {
        for(ll i=1;i<=m;i++) {
            f[k][v[i]]=min(f[k][v[i]],f[k-1][u[i]]+w[i]);
        }
    }

    for(ll i=1;i<=n;i++) {
        if(f[n][i]>=inf) continue;
        tmp=-inf;
        for(ll k=0;k<=n-1;k++) {
            tmp=max(tmp,(f[n][i]-f[k][i])/(n-k));
        }
        ans=min(ans,tmp);
    }

    printf("%.8f\n",ans);

    return 0;
}

代码（0/1分数规划 20pts ）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll N=3e3,M=1e4;

ll n,m,u,v,flg,tot,h;

double w,l,r,mid;

double f[N+5],wt[M*2+5];

ll ver[M*2+5],nxt[M*2+5],head[N+5],vis[N+5],cnt[N+5];

queue<ll> q;

void spfa(ll s) {
    for(ll i=1;i<=n;i++) f[i]=(double)1e12;
    f[s]=0;q.push(s);
    while(!q.empty()) {
        h=q.front();q.pop();vis[h]=0;
        for(ll i=head[h];i;i=nxt[i]) {
            if(f[ver[i]]>f[h]+wt[i]-mid) {
                f[ver[i]]=f[h]+wt[i]-mid;cnt[ver[i]]=cnt[h]+1;
                if(cnt[ver[i]]>=n) {
                    flg=1;break;
                }
                if(!vis[ver[i]]) {
                    vis[ver[i]]=1;q.push(ver[i]);
                }
            }
        }
        if(flg) break;
    }
}

bool check() {
    flg=0;

    for(ll i=1;i<=n;i++) {
        memset(cnt,0,sizeof(cnt));
    //  memset(f,0,sizeof(f));
        memset(vis,0,sizeof(vis));
        while(!q.empty()) q.pop();
        spfa(i);
        if(flg) break;
    //  f[i]=(ll)1e12;
    }
    if(flg) return 0;
    return 1;
}

void add(ll u,ll v,double w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();scanf("%lf",&w);
        add(u,v,w);
    }

    l=-1e4;r=1e4;

    while(r-l>1e-9) {
        mid=(l+r)/2;
        if(check()) l=mid;
        else r=mid;
    //  printf("mid=%.0f flg=%lld\n",mid,flg);
    }

    printf("%.8f\n",l);

    return 0;
}

代码（0/1 分数规划 100pts）：

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define ll long long
using namespace std;

const ll N=3e3,M=1e4;

ll n,m,u,v,flg,tot,h;

double w,l,r,mid;

double f[N+5],wt[M*2+5];

ll ver[M*2+5],nxt[M*2+5],head[N+5],vis[N+5],cnt[N+5];

queue<ll> q;

void dfs(ll s) {
    vis[s]=1;
    for(ll i=head[s];i;i=nxt[i]) {
        if(f[ver[i]]>f[s]+wt[i]-mid) {
            f[ver[i]]=f[s]+wt[i]-mid;
            if(vis[ver[i]]||flg) {
                flg=1;break;
            }
            dfs(ver[i]);
        }
    }
    vis[s]=0;
}

bool check() {
    flg=0;
    memset(f,0,sizeof(f));
    memset(vis,0,sizeof(vis));
    for(ll i=1;i<=n;i++) {
        dfs(i);
        if(flg) break;
    }
    if(flg) return 0;
    return 1;
}

void add(ll u,ll v,double w) {
    ver[++tot]=v;wt[tot]=w;
    nxt[tot]=head[u];head[u]=tot;
}

inline ll read() {
    ll ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while(ch>='0'&&ch<='9') {ret=(ret<<3)+(ret<<1)+ch-'0';ch=getchar();}
    return ret*f;
}

void write(ll x) {
    if(x<0) {x=-x;putchar('-');}
    if(x>9) write(x/10);
    putchar(x%10+48);
}

int main() {

    n=read();m=read();

    for(ll i=1;i<=m;i++) {
        u=read();v=read();scanf("%lf",&w);
        add(u,v,w);
    }

    l=-1e4;r=1e4;

    while(r-l>1e-9) {
        mid=(l+r)/2;
        if(check()) l=mid;
        else r=mid;
    //  printf("mid=%.0f flg=%lld\n",mid,flg);
    }

    printf("%.8f\n",l);

    return 0;
}