A simple Blog for wyx I've been down the bottle hoping.
SRM 556 1000pts 网络流 翻转源汇
发表于: | 分类: Oi | 评论:0 | 阅读:59

T3 1000pts

非常有趣的一道题

有一个包含 $n$ 个点的图,点的编号分别为 $0$ 到 $n−1$ 。有若干双向边连接两个点,有些边可以经过无限次,有些边最多只能经过(双向)两次。Alice计划从 $a_1$ 到 $a_2$ 进行 $a_n$ 次往返旅行(一次往返旅行即从 $a_1$ 到 $a_2$ ,再从 $a_2$ 回到 $a_1$ )。与此同时,Bob也计划从 $b_1$ 到 $b_2$ 进行 $b_n$ 次往返旅行。请问是否存在一种方案,使得同时满足两人的计划。$4\le n\le 50 1≤a_n,b_n≤50$

首先一个环可以拆成两条从 $a_1$ 到 $a_2$的路径,然后我们有一个显然错误的做法就是直接源点连 $a_1,b_1$ 然后终点连汇点跑最大流然后看这个东西和$2*(a_n+b_n)$的大小关系。

但是这样显然是错误的因为有可能 $a_1$流到 $b_2$ 达到满流。

因此我们再把 $b$的源汇反转一下就行了,有一个非常好想的解释:由于两个点之间的边都是无向边,所以两点直接直接跑出来的最大流显然是相同的,那么第一次可以认为 $a_1$ 向 $b_2$ 流了 $x$ , $b_1$ 向 $a_2$ 流了 $x$.源汇反转之后变成了$a_1$向$b_1$ 流了 $x$,那么显然可以认为是 $b_1$ 流向 $a_1$ 再流向 $b_2$

那么可以认为是存在一条满流的路径的。

更为理性的证明可以看队爷的这个

#include <bits/stdc++.h>
using namespace std ;
const int inf = 0x3f3f3f3f;
const int N = 100+5;
const int M = N * N;
int F[N][N], n;

struct Graph {

    int head[N];
    struct graph{
        int next,to,val;
        graph () {}
        graph (int _next,int _to,int _val)
        :next(_next),to(_to),val(_val){}
    }edge[M];

    inline void add(int x,int y,int z) {
        static int cnt = 1;
        edge[++cnt] = graph(head[x],y,z); head[x] = cnt;
        edge[++cnt] = graph(head[y],x,0); head[y] = cnt;
    }

    int depth[N], S, T, cnt, table[N][2];

    bool BFS() {
        queue <int> q;
        memset(depth,-1,sizeof depth);
        depth[S] = 0; q.push(S);
        while(!q.empty())  {
            int tt = q.front(); q.pop();
            for(int i=head[tt];i;i=edge[i].next) {
                if(depth[edge[i].to] < 0 && edge[i].val) {
                    depth[edge[i].to] = depth[tt] + 1;
                    q.push(edge[i].to);
                }
            }
        }
        return ~depth[T];
    }

    inline int DFS(int x,int f) {
        int w, used = 0;
        if(x == T) return f;
        for(int i=head[x];i;i=edge[i].next) {
            if(depth[edge[i].to] == depth[x] + 1 && edge[i].val) {
                w = DFS(edge[i].to,min(edge[i].val,f-used));
                used += w; 
                edge[i].val -= w;
                edge[i^1].val += w;
                if(used == f) return used;
            }
        }
        depth[x] = -1;
        return used;
    }

    inline int Dinic()  {
        int ans = 0;
        while(BFS())  ans += DFS(S,inf);
        return ans;
    }

    void init() {
        S = n + 1 , T = n + 2;
    }
}g1,g2;

class OldBridges
{
    public:
    string isPossible(vector <string> bridges, int a1, int a2, int an, int b1, int b2, int bn)
    {
        string t;
        for(int i=0;i<bridges.size();++i) {
            t = bridges[i], n = t.size();
            for(int j=0;j<n;++j) {
                if(t[j] == 'N') F[i+1][j+1] = inf;
                else if(t[j] == 'O') F[i+1][j+1] = 2;
                else F[i+1][j+1] = 0;
            }
        }
        g1.init(); g2.init();
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) 
                if(F[i][j])  {
                    g1.add(i,j,F[i][j]);
                    g2.add(i,j,F[i][j]);
                }
        }       
        a1 ++, a2 ++, b1 ++, b2 ++;
        int tmp1 = g1.S, tmp2 = g1.T;
        g1.add(tmp1,a1,2*an);
        g1.add(a2,tmp2,2*an);
        g1.add(tmp1,b1,2*bn);
        g1.add(b2,tmp2,2*bn);
        g2.add(tmp1,a1,2*an);
        g2.add(a2,tmp2,2*an);
        g2.add(tmp1,b2,2*bn);
        g2.add(b1,tmp2,2*bn);
        tmp1 = g1.Dinic(), tmp2 = g2.Dinic();
        if(tmp1 >= 2*(an+bn) && tmp2 >= 2*(an+bn)) t = "Yes";
        else t = "No";
        return t;
    }
 
    
// BEGIN CUT HERE
    public:
    void run_test(int Case) { if ((Case == -1) || (Case == 0)) test_case_0(); if ((Case == -1) || (Case == 1)) test_case_1(); if ((Case == -1) || (Case == 2)) test_case_2(); if ((Case == -1) || (Case == 3)) test_case_3(); if ((Case == -1) || (Case == 4)) test_case_4(); if ((Case == -1) || (Case == 5)) test_case_5(); }
    private:
    template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
    void verify_case(int Case, const string &Expected, const string &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
    void test_case_0() { string Arr0[] = {"XOXX","OXOX","XOXO","XXOX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 1; int Arg3 = 1; int Arg4 = 2; int Arg5 = 3; int Arg6 = 1; string Arg7 = "Yes"; verify_case(0, Arg7, isPossible(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_1() { string Arr0[] = {"XOXX","OXOX","XOXO","XXOX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 2; int Arg3 = 1; int Arg4 = 1; int Arg5 = 3; int Arg6 = 1; string Arg7 = "No"; verify_case(1, Arg7, isPossible(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_2() { string Arr0[] = {"XOXO","OXOX","XOXO","OXOX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 2; int Arg3 = 1; int Arg4 = 1; int Arg5 = 3; int Arg6 = 1; string Arg7 = "Yes"; verify_case(2, Arg7, isPossible(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_3() { string Arr0[] = {"XNXO","NXOX","XOXO","OXOX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 2; int Arg3 = 1; int Arg4 = 1; int Arg5 = 3; int Arg6 = 2; string Arg7 = "No"; verify_case(3, Arg7, isPossible(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_4() { string Arr0[] = {"XOXOO","OXOXO","XOXOO","OXOXO","OOOOX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 2; int Arg3 = 2; int Arg4 = 1; int Arg5 = 3; int Arg6 = 2; string Arg7 = "Yes"; verify_case(4, Arg7, isPossible(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }
    void test_case_5() { string Arr0[] = {"XOOOX","OXOOX","OOXOX","OOOXN","XXXNX"}; vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0]))); int Arg1 = 0; int Arg2 = 4; int Arg3 = 3; int Arg4 = 1; int Arg5 = 2; int Arg6 = 2; string Arg7 = "No"; verify_case(5, Arg7, isPossible(Arg0, Arg1, Arg2, Arg3, Arg4, Arg5, Arg6)); }

// END CUT HERE

}t;
// BEGIN CUT HERE
int main(){
//  cout << t.isPossible({"XOXX","OXOX","XOXO","XXOX"},0,2,1,1,3,1) << endl;
//  return 0;
    OldBridges ___test;
    ___test.run_test(-1);
    return 0;
}
// END CUT HERE

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP