图论——负环与01分数规划

Sightseeing Cows

思路：

01分数规划可以考虑二分答案，先判断边界的范围是（0，1000 ]

再来看二分的过程。

关键就在于判断是否存在一个环点权之和/边权之和>mid，此时答案在右半区间，否则答案在左半区间。

整理一下式子会发现

因为本题里既有点权又有边权，我们可以考虑把每个点的点权放到出边上。即
即把每条边的权重看作是f[i] - mid * t[i] ，问题即转化为图中是否存在正环。

思想跟求负环一样的。

代码：

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e6+7;
const double eps=1e-4;

int n,m;
int wf[maxn];
int h[maxn],e[maxn],wt[maxn],ne[maxn],idx;
double d[maxn];
int q[maxn],cnt[maxn];
bool st[maxn];

void add(int a,int b,int c){
    e[idx]=b,wt[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool check(double mid){
    memset(d,0,sizeof d);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
    queue<int>q;
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=1;
    }
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=0;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]<d[t]+wf[t]-mid*wt[i]){
                d[j]=d[t]+wf[t]-mid*wt[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return 1;
                if(!st[j]){
                    st[j]=1;
                    q.push(j);
                }
            }
        }
    }
    return 0;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>wf[i];
    memset(h,-1,sizeof h);
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);//单向边
    }
    double l=0,r=1e6;
    while(r-l>eps){
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    printf("%.2f\n",l);
    return 0;
}

Word Rings （建图的特殊性）

思路：

也是一道01分数规划问题，但关键在于如何建图。

因为匹配的时候只是考虑首尾两个字母，对于一个字符串我们可以分别以首尾两个字母为起点和终点，字符串长度为边的权重建图。

比如ababc，就可以建ab->bc 的长度为5的边。

建图完成后，再看如何求解该问题。问题转化为求所有的边权之和/1最大值。

先看二分的范围是（0，1000 ]

跟上题类似：当

答案在右半区间，反之在左半区间。

可以重新定义边权为w[i]-mid，看图中是否存在正环。

优化可以用之前提到的把SPFA的队列换成栈，真玄学优化。

#include<bits/stdc++.h>
using namespace std;

const int maxn = 700, M = 100010;

int n;
int h[maxn], e[M], w[M], ne[M], idx;
double d[maxn];
int q[maxn], cnt[maxn];
bool st[maxn];

void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool check(double mid){
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);
   int hh=0,tt=0;
    for(int i=0;i<676;i++){
        q[tt++]=i;
        st[i]=1;
    }
    int count=0;
    while(hh!=tt){
        int t=q[hh++];
        if(hh==maxn) hh=0;
        st[t]=0;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(d[j]<d[t]+w[i]-mid){
                d[j]=d[t]+w[i]-mid;
                cnt[j]=cnt[t]+1;
                if(++count>10000) return 1;
                if(cnt[j]>=700) return 1;
                if(!st[j]){
                    st[j]=1;
                   q[tt++]=j;
                   if(tt==maxn) tt=0;
                }
            }
        }
    }
    return 0;
}

int main(){
    char str[1100];
    while(scanf("%d",&n),n){
        memset(h,-1,sizeof h);
        idx=0;
        for(int i=0;i<n;i++){
            scanf("%s",str);
            int len=strlen(str);
            if(len>=2){
                int left=(str[0]-'a')*26+str[1]-'a';
                int right=(str[len-2]-'a')*26+str[len-1]-'a';
                add(left,right,len);
            }
        }
        if(!check(0)) puts("No solution");
        else{
            double l=0,r=1000;
            while(r-l>1e-4){
                double mid=(l+r)/2;
                if(check(mid)) l=mid;
                else r=mid;
            }
            printf("%.10f\n",r);
        }
    }
    return 0;
}