ACM竞赛中的逆向思维

约定不等于承诺〃 2022-08-09 14:56 225阅读 0赞

在竞赛过程中，尤其是近期训练，遇到了不少一定要用逆向思维才能解决的题目。  
为此做一系列的总结。希望能够对大家有所帮助。  
同时，我也会做成PPT，供14级训练使用。

其中有部分问题摘自于2005年国家集训队唐文斌的《正难则反–浅谈逆向思维在解题中的应用》论文。

## 容斥方面 ##

逆向思维在容斥方面的应用相当广泛，也可以说容斥就是逆向思维的一种体现。

### [HDU 5072 Coprime 同色三角形][HDU 5072 Coprime] ###

#### 题目大意： ####

给了n个不同的数，要求有多少个三元组，**两两互质** 或者 **两两不互质**。

#### 思路： ####

原形是同色三角形问题。  
总的三角形的个数是C(n,3)，只需减去不同色的三角形即可。这就是逆向思维。  
对于每个点(数)，与它互质的连红边，不互质的连蓝边，那么对于该点不同色三角形个数为蓝边数∗红边数2。除以2的原因是，对于同一个三角形，我们枚举点的时候被计算了两次。  
那么同色三角形个数为C3n−∑蓝边数∗红边数2。

问题就变成了：  
如何求 原来序列里面的n个数跟某个数k不互质的个数（互质的就是n−k了）？

可以将原来的n个数，每一个都把他们的不同的质因数都求出来，然后枚举它们能够组合的数（1<<cnt），用一个数组num记录，每枚举到一个数，那么数组对应的就\+1

对于数k，也把它的不同质因数求出来，同样枚举它能够组合的所有数t，然后奇加偶减num。

#include<bits/stdc++.h>
    typedef long long ll;
    const int N = 200005;
    
    int p[N][15], vis[N], a[N], num[N];
    int n;
    void Prime()
    {
        memset(vis, 0, sizeof vis);
        for(int i = 0; i < N; ++i) p[i][0] = 0;
        for(int i = 2; i < N; ++i) if(!vis[i])
            {
                p[i][ ++p[i][0] ] = i;
                for(int j = i + i; j < N; j += i)
                {
                    vis[j] = 1;
                    p[j][ ++p[j][0] ] = i;
                }
            }
        p[0][ ++p[0][0] ] = 1;    //考虑0的情况
    }
    
    void init()
    {
        memset(num, 0, sizeof num);
        for(int k = 0; k < n; ++k)
        {
            int now = a[k];
            int cnt = p[ now ][0];
            for(int i = 1; i < (1 << cnt); ++i)
            {
                int t = 1;
                for(int j = 0; j < cnt; ++j) if((1 << j) & i)
                    {
                        t *= p[ now ][j + 1];
                    }
                num[t]++;
            }
        }
    }
    
    void solve()
    {
        ll ans = 0, res, sum = 0;
        ans = (ll)n * (n - 1) * (n - 2) / 6;
        int tot = 0;
        for(int k = 0; k < n; ++k)
        {
            int now = a[k];
            int cnt = p[now][0];
            res = 0;
            for(int i = 1; i < (1 << cnt); ++i)
            {
                int t = 1, g = 0;
                for(int j = 0; j < cnt; ++j) if((1 << j) & i)
                    {
                        t *= p[ now ][j + 1];
                        g++;
                    }
                if(g & 1)  res += num[t];
                else       res -= num[t];
            }
    
            if(res == 0) continue;
            sum += (res - 1) * (n - res);
        }
        printf("%lld\n", ans  - sum / 2);
    
    }
    int main()
    {
        int T;
        scanf("%d", &T);
        Prime();
        while(T --)
        {
            scanf("%d", &n);
            for(int i = 0; i < n; ++i) scanf("%d", &a[i]);
            init();
            solve();
        }
    }

### [ZOJ 1442 Dinner is Ready 不等式解集][ZOJ 1442 Dinner is Ready] ###

此问题的思路来源于唐文斌论文。

#### 题目大意： ####

妈妈烧了M根骨头分给n个孩子们，第i个孩子有两个参数Mini和Maxi，分别表示这个孩子至少要得到Mini根骨头，至多得到Maxi根骨头。  
输出一个整数，表示妈妈有多少种分配方案（骨头不能浪费，必须都分给孩子们）。

#### 思路： ####

这题的模型确实很简单，即求如下方程组的整数解个数。

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∑i=1nXi=MMin1≤X1≤Max1Min2≤X2≤Max2…Minn≤Xn≤Maxn

我们也知道，方程组简单形式

⎧⎩⎨⎪⎪⎪⎪∑i=1nXi=MXi≥0

的整数解个数是  Cn−1M\+n−1 ，(用隔板法就行)。

于是我们做出变形。  
令Yi=Xi\+Mini，则原方程转化为

⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪∑i=1nYi=M−∑i=1nMini0≤Y1≤Max1−Min10≤Y2≤Max2−Min2…0≤Yn≤Maxn−Minn

所以我们可以通过换元法，让下界的限制变成得到简单形式。  
但是很遗憾的是，对于上界的限制，我们无法直接计算出答案。

#### 逆向思维 ####

咱们知道有下界是可以通过换元法变形的。  
设S为全集，表示满足Xi≥Mini的整数解集。  
设Si为S中满足约束条件Xi≤Maxi的整数解的集合，Si¯¯¯¯为Si在S中的补集，即满足Xi>Maxi。  
从上文我们知道|Si|无法直接计算，但是，|Si¯¯¯¯|是一个只有下界约束的简单形式，所以可解。  
我们希望把|Si|的计算转化为|Si¯¯¯¯|的计算。  
于是根据容斥有：

Answer=|S1⋂S2⋂S3…⋂Sn|=|S|−(∑i=1n|si¯¯¯|)\+∑i=1n∑j=i\+1n|Si¯¯¯¯⋂Sj¯¯¯¯|−⋯\+(−1)n×|S1¯¯¯¯⋂S2¯¯¯¯⋂…⋂Sn¯¯¯¯|

。

至此，问题已经解决。  
我们通过逆向思维，在原集合的模|Si|不可解的情况下，通过可解的|Si¯¯¯¯|得到答案。  
时间复杂度为O(2n×(n\+M))。

import java.io.*;
    import java.math.*;
    import java.util.*;
    import java.text.*;
    import java.lang.*;
    public class Main
    {
        static BigInteger zero = BigInteger.ZERO;
        static BigInteger one = BigInteger.ONE;
        static BigInteger two = one.add(one);
    
        public static BigInteger C(BigInteger m,BigInteger n)
        {
            BigInteger ans = one;   
            for(BigInteger i = one; i.compareTo(n)<=0; i = i.add(one))
            {
                BigInteger tp = m.subtract(i).add(one);
                ans = ans.multiply(tp);
                ans = ans.divide(i);
            }
            return ans;
        }
    
        public static BigInteger cal(BigInteger m,BigInteger n)
        {
            return C(m.add(n).subtract(one),n.subtract(one));
        }
    
        public static void main(String arg[]) throws IOException
        {
            BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
            int T = Integer.parseInt(cin.readLine());
            int n;
            BigInteger m,a,limit[] = new BigInteger [20];
            while(T>0)
            {
                T--;
                String ch = cin.readLine();
                StringTokenizer check = new StringTokenizer(ch);
                n = Integer.parseInt(check.nextToken());
                m = new BigInteger(check.nextToken());
    
                int i, j;
                for(i = 1; i<=n; i++)
                {
                    ch = cin.readLine();
                    check = new StringTokenizer(ch);
                    a = new BigInteger(check.nextToken());
                    limit[i] = new BigInteger(check.nextToken());
                    limit[i] = limit[i].subtract(a);
                    m = m.subtract(a);
                }
                if(m.compareTo(zero)<0)
                    System.out.println("0");
                else if(m.compareTo(zero)==0)
                    System.out.println("1");
                else
                {
                    BigInteger sum = zero;
                    for(i = 1; i<=n; i++)
                        sum = sum.add(limit[i]);
                    if(sum.compareTo(m)<0)
                    {
                        System.out.println("0");
                        continue;
                    }
                    BigInteger ans = zero, tp;
                    for(i = 0; i<(1<<n); i++)
                    {
                        int ct = 0;
                        tp = m;
                        for(j = 0; j<n; j++)
                        if((i&(1<<j))!=0)
                        {
                            ct++;
                            tp = tp.subtract(limit[j+1].add(one));
                        }
                        if(tp.compareTo(zero)>=0)
                        {
                            if((ct&1)!=0)
                                ans = ans.subtract(cal(tp,BigInteger.valueOf(n)));
                            else
                                ans = ans.add(cal(tp,BigInteger.valueOf(n)));
                        }
                    }
                    System.out.println(ans);
                }
            }
        }
    
    }

# 搜索方面的应用 #

一般来说，正常的时候都是顺着题意进行搜索或者记忆化。但是很多时候，正向搜索是并不能取得良好的效果的，尤其是搜索配上策略的时候。  
需要仔细考虑是否正向搜索可以得到正确的策略。如果正向搜索实在不行，可以想一想是否有逆向搜索的解决办法。

### [2015-2016 ACM-ICPC, NEERC, Moscow Subregional Contest K. King’s Rout][2015-2016 ACM-ICPC_ NEERC_ Moscow Subregional Contest K. King_s Rout] ###

#### 题目大意： ####

给了你一个拓扑结构。希望你构造出一种符合以下条件的拓扑序。  
1、拓扑序  
2、在满足上述条件的情况下，让1尽可能地靠前。  
3、在满足上述条件的情况下，让2尽可能地靠前。  
…  
n、在满足上述条件的情况下，让n尽可能地靠前。

#### 思路： ####

用贪心地方法进行一般的拓扑排序。  
比如，直接用小根堆维护拓扑排序过程。  
比如，将1节点的所以前驱节点取出进行小根堆维护的拓扑排序。  
有很多种贪心的策略，但是没一个是对的。

#### 逆向思维： ####

逆拓扑序字典序最大。  
用大根堆直接维护拓扑排序，倒着输出即可。  
正向的贪心策略有问题，逆向的贪心策略则是合法的。

#include<bits/stdc++.h>
    
    using namespace std;
    
    const int MAXN=200010;
    
    typedef vector<int> vi;
    typedef pair<int, int> pii;
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    
    priority_queue<int> q;
    int ans[MAXN],cnt;
    int deg[MAXN];
    vi g[MAXN];
    int n,m;
    map<pii,int> ma;
    
    void toposort()
    {
        for(int i=1; i<=n; i++)
            if(deg[i]==0)
                q.push(i);
        while(!q.empty())
        {
            int u=q.top();
            q.pop();
            ans[cnt++]=u;
            for(auto v:g[u])
            {
                if(--deg[v]==0)
                    q.push(v);
            }
        }
    }
    
    int main()
    {
        scanf("%d %d",&n,&m);
        for(int i=1,a,b; i<=m; i++)
        {
            scanf("%d %d",&a,&b);
            if(ma.find(mp(a,b))==ma.end())
            {
                ma[(mp(a,b))]=1;
                g[b].pb(a);
                deg[a]++;
            }
        }
        toposort();
        for(int i=cnt-1; i>=0; i--)
            printf("%d ",ans[i]);
        puts("");
        return 0;
    }

### [2014-2015 ACM-ICPC, Asia Xian Regional Contest H. The Problem to Make You Happy][2014-2015 ACM-ICPC_ Asia Xian Regional Contest H. The Problem to Make You Happy] ###

#### 题目大意 ####

博弈  
在一张有向图，在图中的两个节点上面有两个棋。Alice和Bob在上面移动棋子，如果有人不能移动，那就输了。如果两个棋子在同一个节点上就是Alice赢了，如果游戏无法结束就是Bob赢了。

#### 思路 ####

可以用原来计算SG函数的方法进行记忆化搜索。  
你从起点开始记忆化搜索，是做不出来的。  
总是有反例。

#### 逆向思维 ####

从**必败态**反向搜索。  
状态就是 f\[bob\]\[alice\]\[who\]， 维护一个**必败态**(对于Bob来说)集合，初始里面只有f\[x\]\[x\]\[whatever\] ，f\[x\]\[y\]\[alice′s turn\] （x 出度为0）（Bob走不动了），然后不断扩展到扩展不动就行了。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define getidx(l,r) (l+r | l!=r)
    #define ls getidx(l,mid)
    #define rs getidx(mid+1,r)
    #define lson l,mid
    #define rson mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    struct P
    {
        int a, b, c;
        P() {}
        P(int a,int b,int c):a(a),b(b),c(c) {}
    };
    const int N = 233;
    bool g[N][N];
    int n, m;
    int out[N];
    int a, b;
    int f[N][N][2]; /// f[bob][alice][现在轮到谁走(0:alice 1:bob)] = 1 : Bob 必败
    int cnt[N][N];
    int main()
    {
        int T,ca=1;
        cin>>T;
        while (T--)
        {
            cin>>n>>m;
            CLR(g, false);
            CLR(out, 0);
            while (m--)
            {
                int u, v;
                scanf("%d%d", &u, &v);
                g[v][u] = true;
                out[u] ++;
            }
            cin >> a >> b;
            printf("Case #%d: ", ca++);
            queue <P> q; /// q 中是所有必败态（对于Bob来说）
    
            CLR(f, 0);
            CLR(cnt, 0);
            for(int i=1;i<=n;i++)
            {
                f[i][i][0] = 1;
                q.push(P(i,i,0));
                f[i][i][1] = 1;
                q.push(P(i,i,1));
            }
            for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if (i - j && out[i]==0)
            {
                f[i][j][0] = 1;
                q.push(P(i,j,0));
            }
            while (!q.empty())
            {
                P u = q.front();
                q.pop();
                int x = u.a, y = u.b, z = u.c;
                if (z == 1)   /// Last turn is Bob's turn
                {
                    for(int j=1;j<=n;j++) if (g[x][j])   /// Last move : Bob : j --> x
                    {
                        if ( ++cnt[j][y] == out[j])   /// (j,y)这个状态，Bob无论怎么走都是必败态
                        {
                            if (f[j][y][0]) continue;
                            f[j][y][0] = 1;
                            q.push(P(j, y, 0));
                        }
                    }
                }
                else   /// Last turn is Alice's turn
                {
                    for(int j=1;j<=n;j++) if (g[y][j])   /// Last move : Alice : j --> y
                    {
                        if (f[x][j][1]) continue; /// Alice可以选择一条路使得Bob必败
                        f[x][j][1] = true;
                        q.push(P(x, j, 1));
                    }
                }
            }
            if (f[a][b][0]) puts("No");
            else puts("Yes");
        }
        return 0;
    }

# 记录变量方面 #

很多题目变量的性质你直接记录根本就没法算。  
比如下面的概率题。

### [HDU 5245 Joyful][] ###

#### 题目大意： ####

给你一个M×N的矩阵，你可以选K次，每次选择两个点(x1,y1)和(x2,y2)，将这两个点围成的子矩阵涂上颜色。  
求涂色的格子的个数。

#### 思路： ####

这题就像最基本的概率题一样，有10个电灯泡，每个电灯泡是坏的概率是p，问你这些的电灯泡至少有一个是好的的概率是多少。  
直接算挺麻烦的。要用相对事件的概率算。  
每个电灯泡都是坏的概率是p10，则至少有一个是好的概率是1−p10。

所以你就计算每个格子不被选中的概率。

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<50
    #define speed std::ios::sync_with_stdio(false);
    
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define CPY(x,y) memcpy(x,y,sizeof(x))
    #define clr(a,x,size) memset(a,x,sizeof(a[0])*(size))
    #define cpy(a,x,size) memcpy(a,x,sizeof(a[0])*(size))
    #define debug(a) cout << #a" = " << (a) << endl;
    #define debugarry(a, n) for (int i = 0; i < (n); i++) { cout << #a"[" << i << "] = " << (a)[i] << endl; }
    
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    
    #define MID(x,y) (x+((y-x)>>1))
    #define getidx(l,r) (l+r | l!=r)
    #define ls getidx(l,mid)
    #define rs getidx(mid+1,r)
    #define lson l,mid
    #define rson mid+1,r
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    int m, n, k;
    double ans, c[502][502];
    
    double calc(double x, int p)
    {
        double res = 1.0;
        while (p)
        {
            if (p&1) res = res*x;
            p >>= 1; x = x*x;
        }
        return res;
    }
    
    int main()
    {
        //freopen("data.in", "r", stdin);
        //freopen("data.out","w", stdout);
        int T, cnt = 0;
        scanf("%d", &T);
        while (T--)
        {
            cnt++;
            scanf("%d %d %d", &m, &n, &k);
            double tot = 1;
            tot = tot*m*m*n*n;
            for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                double tmp, sum = 0;
                if (j-1 >= 1)
                {
                    tmp = (j-1)*m;
                    sum += tmp*tmp;
                }
                if (j+1 <= n)
                {
                    tmp = (n-j)*m;
                    sum += tmp*tmp;
                }
                if (i-1 >= 1)
                {
                    tmp = (i-1)*n;
                    sum += tmp*tmp;
                }
                if (i+1 <= m)
                {
                     tmp = (m-i)*n;
                     sum += tmp*tmp;
                }
                tmp = (i-1)*(j-1);
                sum -= tmp*tmp;
                tmp = (i-1)*(n-j);
                sum -= tmp*tmp;
                tmp = (j-1)*(m-i);
                sum -= tmp*tmp;
                tmp = (n-j)*(m-i);
                sum -= tmp*tmp;
                c[i][j] = sum/tot;
            }
            ans = 0;
            for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
            {
                c[i][j] = calc(c[i][j], k);
                ans += (1-c[i][j]);
            }
            printf("Case #%d: %.0lf\n", cnt, ans);
        }
        return 0;
    }

### [2015-2016 ACM-ICPC, NEERC, Moscow Subregional Contest H. Hashing][2015-2016 ACM-ICPC_ NEERC_ Moscow Subregional Contest H. Hashing] ###

#### 题目大意： ####

给你一个16进制表示的数组。然后给你选出一些来进行hashing。哈希函数如下：

![这里写图片描述][80f625727c863af6d90c10d3e6be49bd93e274ce.png]  
  
其中  si 为选出的数的下标，是一个单调上升的序列，  i 为  si 的下标。

#### 思路： ####

一开始有一个猜想，当n到达一定会程度的时候所有的数都选上最优。  
剩下的就可以用O(n3)的dp或者O(n2)的斜率优化来做。  
但是很遗憾的是，这样个猜想是错的。

#### 逆向思维： ####

我们发现，如果我们记录选中了多少个是O(n2)的空间复杂度，是肯定不可行的，时间复杂度也不够。  
根据上面那个错误的猜想，我们可以继续猜想：不被选中的数的个数特别少。少到多少呢？这个不太好猜，但是肯定不会大于256。  
所以我们就可以记录不被选中的数。  
因此就可以用dp直接做了。

#include<bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    int n;
    int a[100005];
    ll ans, f[100005][205];
    
    int main()
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%x", &a[i]);
        for (int i = 1; i <= n; i++)
        for (int j = 0; j<= min(i, 200); j++)
        {
            if (j > 0) f[i][j] = f[i-1][j-1];
            f[i][j] = max(f[i][j], f[i-1][j]+(a[i]^(i-j-1)));
            ans = max(f[i][j], ans);
        }
        printf("%lld\n", ans);
        return 0;
    }

### [SGU 236 Greedy Path][] ###

此题摘自唐文斌论文。

#### 题目大意： ####

有n个城市，被m条路连接着。最近成立了一些旅行社，在这些城市之间给旅行者们提供服务。旅行者从城市i到城市j需要付给旅行社的费用是Cij，需要的时间为Tij 。很多旅行者希望加入旅行社，但是旅行社只有一辆车。于是旅行社的老板决定组织一次旅行大赚一笔。公司里的专家需要提供一条使得贪心函数F(G)最大的回路G。F(G) 等于总花费除以总时间。但是没有人找到这样的回路，于是公司的领导请你帮忙。  
输入：  
第一行包含两个数n(3≤n≤50),m 分别表示点数和边数。  
接下来m行每行包含一条路的描述。  
输入四个数,A,B,CAB,TAB（0≤CAB≤100，0≤TAB≤100）  
输出：  
如果不存在这样的路，输出0。  
否则输出回路中包含的城市个数，然后依次输出通过的城市的顺序。如果有很多条这样的路，输出任意一条。

#### 思路： ####

题目要求是求一条回路，但不是边权和最大或者最小，所以我们不能直接使用经典算法。  
设G=(V,E)，S为G中所有回路C=(V′,E′)组成的集合。我们的目标是找到集合S中的一条回路使得F(C)取到最大值：

![这里写图片描述][20151116213632707]

#### 逆向思维： ####

如果我们知道C∗=(V∗,E∗)∈S是一条最优回路，那么

![这里写图片描述][20151116213757575]  
于是我们定义函数  o(t) :

o(t)=maxC=(V′,E′)∈S∑e∈E′Ce−t∑e∈E′Te

我们做一个猜想：如果有  o(t∗)=0 ，那么存在  C∗=(V∗,E∗)∈S 满足

t∗=∑e∈E∗Ce∑e∈E∗Te

我们认为  C∗ 就是一条最优回路。

![这里写图片描述][20151116214735756]  
于是我们就得到了算法：  
我们从一个包含  t∗ 的区间  (tl,th) 开始。（例如  tl=mine∈ECeTe,th=maxe∈ECeTe ）  
每一次，选取  tl 与  th 的中点  t , 计算  O(t) 。  
 O(t) 的计算方法：  
对于边  e∈E , 设一个新的参数  We=Ce–t∗Te  
用Floyd算法计算有向图的最大权值环。该最大权值即  O(t) 。  
根据性质一，更新  tl 或  th , 得到新的上下界，继续二分，直到达到精度要求。

假设二分的次数为K , 则算法的时间复杂度为O(K∗n3)。这虽然不是一个严格的多项式算法，但是对于题目给定的范围，该算法可以很快地求出答案。

#include<cstdio>
    #include<algorithm>
    #include<queue>
    #include<cstring>
    using namespace std;
    
    typedef double ld;
    const int NUM=100+10;
    const int MAX=NUM*NUM;
    const ld EPS=1e-10;
    const ld INF=1e10;
    
    int n,m;
    
    int begin[NUM],next[MAX],t[MAX],ti[MAX],co[MAX],tot;
    ld w[MAX];
    
    void add(int u,int v,int cost,int time)
    {
        t[++tot]=v;
        next[tot]=begin[u];
        begin[u]=tot;
        co[tot]=cost;
        ti[tot]=time;
    }
    
    int hash[MAX],pre[MAX],num[MAX],onenode;
    ld dist[NUM];
    
    queue<int> q;
    
    int check(ld mid)
    {
        memset(hash,0,sizeof hash);
        memset(num,0,sizeof num);
        memset(pre,0,sizeof pre);
        int i,u,v;
        for(i=1;i<=tot;++i)w[i]=mid*ti[i]-(ld)co[i];
    
        while(!q.empty())q.pop();
        for(i=1;i<=n;++i)dist[i]=INF;
    
        dist[1]=0;q.push(1);++num[1];pre[1]=0;
    
        while(!q.empty())
        {
            u=q.front();q.pop();
            hash[u]=0;
            if(num[u]>n+1)return u;
            for(i=begin[u];i;i=next[i])
            {
                v=t[i];
                if(dist[v]>dist[u]+w[i])
                {
                    dist[v]=dist[u]+w[i];
                    pre[v]=u;
                    if(!hash[v])
                    {
                        hash[v]=1;
                        q.push(v);
                        ++num[v];
                    }
                }
            }
        }
    
        return 0;
    }
    
    int ans[MAX];
    
    int main()
    {
        #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
        #endif
        int i,x,y,cc,tt;
        scanf("%d %d",&n,&m);
        for(i=1;i<=m;++i)
        {
            scanf("%d %d %d %d",&x,&y,&cc,&tt);
            add(x,y,cc,tt);
        }
        ld l=EPS,r=INF,mid;
        while(r-l>EPS)
        {
            mid=(l+r)/2;
            if(check(mid))l=mid;
            else r=mid;
        }
    
        int now=check(l);
        if(!now)
        {
            printf("0\n");
            return 0;
        }
        memset(hash,0,sizeof hash);
    
        while(hash[now]<=1)
        {
            ++hash[now];
            if(hash[now]==2)ans[++ans[0]]=now;
            now=pre[now];
        }
    
        printf("%d\n",ans[0]);
        for(i=ans[0];i>=1;--i)
            printf("%d ",ans[i]);
        printf("\n");
    }

[HDU 5072 Coprime]: http://acm.hdu.edu.cn/showproblem.php?pid=5072
[ZOJ 1442 Dinner is Ready]: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1442
[2015-2016 ACM-ICPC_ NEERC_ Moscow Subregional Contest K. King_s Rout]: http://codeforces.com/gym/100792/problem/K
[2014-2015 ACM-ICPC_ Asia Xian Regional Contest H. The Problem to Make You Happy]: http://codeforces.com/gym/100548/attachments
[HDU 5245 Joyful]: http://acm.hdu.edu.cn/showproblem.php?pid=5245
[2015-2016 ACM-ICPC_ NEERC_ Moscow Subregional Contest H. Hashing]: http://codeforces.com/gym/100792/problem/H
[80f625727c863af6d90c10d3e6be49bd93e274ce.png]: /images/20220731/ca70a8615d924a9e89900f41461c3a3f.png
[SGU 236 Greedy Path]: http://acm.sgu.ru/problem.php?problem=236
[20151116213632707]: /images/20220731/e646229c95134bddbfa4d30a58eab31b.png
[20151116213757575]: /images/20220731/9ca697d9dbdb4e37851ca9dadc11e32a.png
[20151116214735756]: /images/20220731/cab698e484e341aeaa9f72a35a85192d.png