题目链接

Andrew Stankevich Contest 22 A. Maximal Flows Dimension

题目大意

回顾网络流的定义：一张图的流函数 \(f:E\rightarrow \mathbb{R}\)，是满足 容量限制、斜对称性、流量守恒性 的函数，即：

\[f(u,v) \leq c(u,v)\\ f(u,v) = -f(v,u)\\ \forall x\in V-\{S,T\},\;\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v) \]

流的大小定义为 \(\sum_{(s,v)\in E}f(s,v)\)，其中流的加法和标量乘法定义为 对应函数值的 加法和乘法。

现在固定下任意一个最大流 \(f_{max}\)，若一个最大流集合 \(\{f_1,f_2,...,f_n\}\) 满足任意一个最大流都可以表示为如下形式，且是极小的，则称之为最大流的一组基：

\[f=f_{max}+\sum_{i=1}^n\alpha_if_i,\;\alpha_i\in\mathbb{R} \]

可以证明基的大小是唯一的，称之为最大流的维度。

现在给定一个 \(n\) 个点，\(m\) 条边的图，求出它的最大流维度。

\(1\leq n,m\leq 10\)，边容量 \(\leq 10^4\) 。

思路

容易发现 \(f\) 和 \(f_{max}\) 的具体取值不重要，我们只要关注差值 \(f-f_{max}\)。

注意到流量守恒的性质依然在 \(f-f_{max}\) 中成立，而由于两者都是最大流，流量相同，所以此时的 \(S\) 和 \(T\) 同样满足流量守恒。而一张所有点的入度等于出度的图，本质是由一系列环组成的，在这里也是，注意到右侧的和式 \(\sum\alpha_if_i\) 本质上亦是如此，所以问题转化为我们要找到一组环的基，能够生成其它的所有环。

考虑哪些环会出现在流的差值中，这相当于是一个最大流转化到另一个最大流的过程，于是想到在 \(dinic\) 求最大流时的残留网络，如果在一个最大流的残留网络上塞一个环上去，就刚好可以得到另外一个最大流，而所有网络流之间都是可以互相转化的（怎么证呢），所以任意一个残留网络上的 所有环的集合 即为 差值中可能出现的环。

在得到所有环之后，考虑怎么求出最小的基。我们将一条边作为向量，每一位记录点的状态，端点处为 \(1\)，剩下的地方为 \(0\)，一系列边构成环 \(\iff\) 向量按位异或和为 \(0\) 。从而所有的环都可以通过这种方式表示出来，我们要做的就是用尽量少的边表示出这些环，其实就是表示出剩下的边，这就是线性基，于是原问题的最大流维度等价于此时的线性基的大小。题目便做完了。

实现时先求一遍最大流，然后在残余网络上找到那些可能被包含在环中的边，即 \(SCC\) 内部的边，然后把它们拉出来跑线性基即可。

时间复杂度 \(O(n^2m)\)，由于每条边只有两处非零，所以实现精细一些应该可以做到 \(O(dinic(n,m)+nm)\) 。

Code

#include<iostream>
#include<cstring>
#include<queue>
#include<stack>
#include<fstream>
#define mem(a,b) memset(a, b, sizeof(a))
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define per(i,b,a) for(int i = (b); i >= (a); i--)
#define N 12
#define Inf 0x3f3f3f3f
using namespace std;

int n, m;
int head[N], nxt[2*N], to[2*N];
int now[N], dis[N], cap[2*N], c[N], dfn[N], low[N];
int cnt, S, T, scc, num;
bool in[N], leftout[N];
queue<int> q;
stack<int> stk;

int base[N];

void init(){ mem(head, -1), cnt = -1; }
void add_e(int a, int b, int c, bool id){
    nxt[++cnt] = head[a], head[a] = cnt, to[cnt] = b, cap[cnt] = c;
    if(id) add_e(b, a, 0, 0);
}

bool bfs(){
    mem(dis, 0), dis[S] = 1;
    q.push(S);
    while(!q.empty()){
        int cur = q.front(); q.pop();
        now[cur] = head[cur];
        for(int i = head[cur]; ~i; i = nxt[i]) if(cap[i])
            if(!dis[to[i]]) dis[to[i]] = dis[cur]+1, q.push(to[i]);
    }
    return dis[T];
}

int dfs(int x, int flow){
    if(x == T) return flow;
    int flown = 0;
    for(int i = now[x]; ~i; i = nxt[i]){
        int y = to[i]; now[x] = i;
        if(!cap[i] || dis[y] != dis[x]+1) continue;
        int t = dfs(y, min(flow - flown, cap[i]));
        cap[i] -= t, cap[i^1] += t;
        flown += t;
        if(flown == flow) break;
    }
    return flown;
}

void tarjan(int x){
    dfn[x] = low[x] = ++num;
    in[x] = true, stk.push(x);
    for(int i = head[x]; ~i; i = nxt[i]) if(cap[i]){
        int y = to[i];
        if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
        else if(in[y]) low[x] = min(low[x], dfn[y]);
        if(c[y]) leftout[i/2+1] = true;
    }
    if(dfn[x] == low[x]){
        int y; ++scc;
        do{
            y = stk.top(); stk.pop();
            in[y] = false, c[y] = ++scc;
        } while(y != x);
    }
}

int main(){
    freopen("dimension.in", "r", stdin);
    freopen("dimension.out", "w", stdout);
    cin>>n>>m;
    int u, v, w; init();
    rep(i,1,m) cin>>u>>v>>w, add_e(u, v, w, 1);

    S = 1, T = n;
    while(bfs()) dfs(S, Inf);
    rep(i,1,n) if(!dfn[i]) tarjan(i);

    int dim = 0;
    rep(i,1,m) if(!leftout[i]){
        dim++;
        int val = 1<<(to[i*2-1]-1) | 1<<(to[i*2-2]-1);
        rep(p,0,n-1) if(val>>p&1)
            if(!base[p]){ base[p] = val, dim--; break; }
            else val ^= base[p];
    }
    cout<< dim <<endl;
    return 0;
}