最短路及其应用

2018寒假集训

E - Going in Cycle!! (UVA - 11090)

n点m边带权有向图，输出其边权和的平均值最小的回路。假设存在一个平均值为x，则这个回路上的k边之和小于kx。可以转化为k边之和减去kx小于0,即求是否存在边权为原边权减去x的负权回路，spfa判一下二分求最小即可。ps:注意高精度二分的格式

#include <iostream>
#include <cstdio>
#include <queue>
#include <map>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
#define eps 1e-4
const int maxn =55;
int n,m,t;
vector<pair<int,double> >E[maxn];
queue<int>mxr;
int vis[maxn],inq[maxn],viss[maxn];
double d[maxn];
void init()
{
    memset(vis,0,sizeof(vis));
    memset(inq,0,sizeof(inq));
    for(int i=0;i<maxn;i++)
    {
        E[i].clear();
        d[i]=1e7+5;;
    }
}
bool spfa(int s)
{
    for(int i=0;i<maxn;i++)
        d[i]=1e7+5;
    memset(inq,0,sizeof(inq));
    mxr.push(s);
    d[s]=0,inq[s]++;
    vis[s]=1;
    while(!mxr.empty())
    {
        int now=mxr.front();
        mxr.pop();
        vis[now]=0;
        viss[now]=1;
        for(int i=0;i<E[now].size();i++)
        {
            int v=E[now][i].first;
            if(d[v]>d[now]+E[now][i].second)
            {
                d[v]=d[now]+E[now][i].second;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(inq[v]>n) return true;
                    inq[v]++;
                    mxr.push(v);
                }
            }
        }
    }
    return false;
}
bool judge(double mid)
{
    memset(viss,0,sizeof(viss));
    for(int i=1;i<=n;i++)
        for(int j=0;j<E[i].size();j++)
            E[i][j].second-=mid;
    bool flag;
    for(int i=1;i<=n;i++)
        if(!viss[i]){
            flag=spfa(i);
            if(flag) break;
        }
    for(int i=1;i<=n;i++)
        for(int j=0;j<E[i].size();j++)
            E[i][j].second+=mid;
    return flag;
}
int main()
{
    int cnt=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        init();
        int a,b;
        double c,l,r;
        l=r=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%lf",&a,&b,&c);
            E[a].push_back(make_pair(b,c));
            r=max(r,c);
        }
        int mxr;
        printf("Case #%d: ",++cnt);
        if(!judge(r+1)) printf("No cycle found.\n");
        else 
        {
            while(r-l>eps)
            {
                double mid=(l+r)/2;
                if(judge(mid))
                {
                    r=mid;
                }
                else
                    l=mid;
            }
            printf("%.2f\n",l);
        }
    }
    return 0;
}

F - Halum (UVA - 11478)

带权有向图，我们进行一个操作选择一个结点和一个值d，操作后所有以这个结点为终点的边权值减小d，以其为起点的边权值加上d，让所有边权的最小值>0！！且尽量大。我们设sum(a)为作用于a上所有d之和。二分答案x，我们可以列出一系列不等式组形如：sum(b)-sum(a)$\le$w(a,b)-x，利用差分约束进行处理即可。。题目很多细节看代码注释。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
using namespace std;
const int maxn = 505;
const int inf = 0x3f3f3f3f;
int n,m,d[maxn],vis[maxn],inq[maxn];
vector<pair<int,int> >E[maxn];
void init()
{
    for(int i=0;i<=n;i++)
    {
        d[i]=inf;
        vis[i]=inq[i]=0;
        E[i].clear();
    }
}
bool spfa(int s)
{
    queue<int>mxr;
    d[s]=0,vis[s]=1;
    inq[s]++;
    mxr.push(s);
    while(!mxr.empty())
    {
        int now=mxr.front();
        mxr.pop();
        vis[now]=0;
        for(int i=0;i<E[now].size();i++)
        {
            int v=E[now][i].first;
            if(d[v]>d[now]+E[now][i].second)
            {
                d[v]=d[now]+E[now][i].second;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(inq[v]>n+1) return false;
                    inq[v]++;
                    mxr.push(v);
                }
            }
        }
    }
    return true;
}
bool solve(int x)
{
    memset(d,inf,sizeof(d));
    memset(vis,0,sizeof(vis));
    memset(inq,0,sizeof(inq));
    for(int i=1;i<=n;i++)
        for(int j=0;j<E[i].size();j++)
            E[i][j].second-=x;
    bool flag=spfa(0);
    for(int i=1;i<=n;i++)
        for(int j=0;j<E[i].size();j++)
            E[i][j].second+=x;
    return flag;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        int u,v,d;
        int l,r,ret;
        l=1;r=-inf;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&d);
            E[u].push_back(make_pair(v,d));
            r=max(r,d);
        }
        for(int i=1;i<=n;i++)
            E[0].push_back(make_pair(i,0));
        if(solve(r+1)) printf("Infinite\n"); 
        else if(!solve(1)) printf("No Solution\n");
        else{
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(solve(mid))
                {
                    ret=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
            printf("%d\n",ret);
        }
        //对特判的分析：首先可以知道存在负环差分约束无解，但是正环可以有解，而图为正环的话，无论如何操作都不可能让最小边>最大边。唯有无环的情况有可能，所以可以直接判断图中有无环来判定inf 
        //而无环的情况是可以直接让最小边无穷大的(画图分析) 所以总结有三种情况讨论：1.带负环 2.带正环 3.无环，前1个if对应无环的分析，后一个二分和if对存在环的分析 ，而存在环的情况是我们主要要讨论的
        //要讨论正环和负环这里直接判负环如果不存在则将答案继续最大化 ，还需要对二分单调性证明， 因为二分答案后问题转化为每条边的权值均不小于x，可以知道如果solve(x)不满足的话solve(x+1)一定不满足
        //显然不小于x都不满足怎么可能满足不小于x+1 
        //ps：蓝书上这里有坑，题意解释为最小值非负，实际题意要求>0 
    }
    return 0;
}