您的位置:澳门威利斯人赌场 > 线上娱乐 > 随想【澳门威利斯人赌场】

随想【澳门威利斯人赌场】

发布时间:2019-09-22 04:54编辑:线上娱乐浏览(88)

    这个电影是清华史,但是放诸北大也无不可。中国近代需实业救国,长远来看终究是文化兴国。所以选文的选文,选理的选理。但是终归是年轻人啊,自己的国家面对生死存亡之际,哪里管得了什么实业,什么文化?只想着一腔热血,为保国家。但是当兵的人,你们的枪不要对着人民,只该对着敌人。中国多灾多难,政策不过是一人制定,但是受难的又是多少百姓??莫忘自己的职责,确实该只凭良心。

    题面戳我

    Solution

    一般这种题就转化成最小割做
    把最大收益转化成最小损失,先把所有收益加入ans

    考虑建图,设S集合为选文的,T为选理的
    单个选的比较简单,就直接连就好了:
    直接令容量(S,x)=选文科的收益,(x,T)=选理科的收益即可。
    那么两个一起选的怎么连?
    设两个人x,y,他们俩一起选文的收益是a,一起选理的收益是b。
    四种情况

    • x,y都选文。此时被割掉的边是(x,T)和(y,T),总损失应为b
    • x,y都选理。此时被割掉的边是(S,x)和(S,y),总损失应为a
    • x选文y选理。此时被割掉的边是(x,T),(S,y)和(x,y),总损失应为a b
    • x选理y选文。此时被割掉的边是(S,x),(y,T)和(y,x),总损失应为a b

    这样就能列出一个方程组:
    [ begin{cases} (x,T) (y, T) = b\ (S, x) (S, y) = a\ (x, T) (S, y) (x, y) = a b\ (S, x) (y, T) (y, x) = a b\ end{cases} ]

    显然无解,这是不定方程
    考虑到不影响其它边,那么取任意一组可行解就好
    [ (x, T) = frac {b}{2}\ (y, T) = frac {b}{2}\ (S, x) = frac {a}{2}\ (S, y) = frac {a}{2}\ (x, y) = frac {a b}{2}\ (y, x) = frac {a b}{2}\ ]

    连完跑最大流即可

    # include <bits/stdc  .h>
    # define IL inline
    # define RG register
    # define Fill(a, b) memset(a, b, sizeof(a))
    # define Copy(a, b) memcpy(a, b, sizeof(a))
    using namespace std;
    typedef long long ll;
    const int _(100010), __(1e6   10), INF(2147483647);
    
    IL ll Read(){
        RG char c = getchar(); RG ll x = 0, z = 1;
        for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
        for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1)   (x << 3)   (c ^ 48);
        return x * z;
    }
    
    int n, m, ans, id[110][110], num, val[6][110][110];
    int w[__], fst[_], nxt[__], to[__], cnt, S, T, lev[_], cur[_];
    queue <int> Q;
    
    IL void Add(RG int u, RG int v, RG int f, RG int _f){
        w[cnt] = f; to[cnt] = v; nxt[cnt] = fst[u]; fst[u] = cnt  ;
        w[cnt] = _f; to[cnt] = u; nxt[cnt] = fst[v]; fst[v] = cnt  ;
    }
    
    IL int Dfs(RG int u, RG int maxf){
        if(u == T) return maxf;
        RG int ret = 0;
        for(RG int &e = cur[u]; e != -1; e = nxt[e]){
            if(lev[to[e]] != lev[u]   1 || !w[e]) continue;
            RG int f = Dfs(to[e], min(w[e], maxf - ret));
            ret  = f; w[e ^ 1]  = f; w[e] -= f;
            if(ret == maxf) break;
        }
        return ret;
    }
    
    IL bool Bfs(){
        Fill(lev, 0); lev[S] = 1; Q.push(S);
        while(!Q.empty()){
            RG int u = Q.front(); Q.pop();
            for(RG int e = fst[u]; e != -1; e = nxt[e]){
                if(lev[to[e]] || !w[e]) continue;
                lev[to[e]] = lev[u]   1;
                Q.push(to[e]);
            }
        }
        return lev[T];
    }
    
    int main(RG int argc, RG char* argv[]){
        n = Read(); m = Read(); Fill(fst, -1); T = n * m   1;
        for(RG int i = 1; i <= n;   i)
            for(RG int j = 1; j <= m;   j)
                id[i][j] =   num;
        for(RG int p = 0; p < 6;   p){
            RG int x = n - ((p == 2) | (p == 3)), y = m - ((p == 4) | (p == 5));
            for(RG int i = 1; i <= x;   i)
                for(RG int j = 1; j <= y;   j){
                    val[p][i][j] = Read(), ans  = val[p][i][j];
                    if(p == 0) Add(S, id[i][j], val[p][i][j] << 1, 0);
                    if(p == 1) Add(id[i][j], T, val[p][i][j] << 1, 0);
                    if(p == 3){
                        RG int xx = id[i][j], yy = id[i   1][j], b = val[p][i][j], a = val[p - 1][i][j];
                        Add(xx, T, b, 0); Add(yy, T, b, 0);
                        Add(S, xx, a, 0); Add(S, yy, a, 0);
                        Add(xx, yy, a   b, a   b);
                    }
                    if(p == 5){
                        RG int xx = id[i][j], yy = id[i][j   1], b = val[p][i][j], a = val[p - 1][i][j];
                        Add(xx, T, b, 0); Add(yy, T, b, 0);
                        Add(S, xx, a, 0); Add(S, yy, a, 0);
                        Add(xx, yy, a   b, a   b);
                    }
                }
        }
        for(ans <<= 1; Bfs(); ) Copy(cur, fst), ans -= Dfs(S, INF);
        printf("%dn", ans >> 1);
        return 0;
    }
    

    本文由澳门威利斯人赌场发布于线上娱乐,转载请注明出处:随想【澳门威利斯人赌场】

    关键词: