控制公司 Controlling Companies

\(USACO\) 上 \(CHAPTER 2\)

的题

黄题难度 但我写了一个网络流

看了下题解 只有我是写的网络流

其他好像都是搜索

思想

网络流中进行是否可以増广和増广是

即(我写的\(dinic\))DINIC中的\(BFS\)和\(DFS\)

判断是否可以走的时候 改成

if(depth[v = edge[e].v] == -1&&(edge[e].w&&able[tp]))//BFS
if(depth[v = edge[e].v] == depth[x] + 1&&(edge[e].w&&able[x]))//DFS

就行了 还有一些要注意的点 各位神仙写的时候很容易想到

对了 我用了\(set\)优化

可去重 可排序 为什么不用呢？

时间复杂度

\(O(min(N^{0.67},M^{0.5}) * M*N^2)\)

时间复杂度不比搜索优秀 但练练网络流也挺好的

#include <set>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define reg register int
#define isdigit(x) ('0' <= x&&x <= '9')
template<typename T>
inline T Read(T Type)
{
    T x = 0,f = 1;
    char a = getchar();
    while(!isdigit(a)) {if(a == '-') f = -1;a = getchar();}
    while(isdigit(a)) {x = (x << 1) + (x << 3) + (a ^ '0');a = getchar();}
    return x * f;
}
const int MAXN = 10000;
int n,cnt,ori_[MAXN];
struct node
{
    int v,w,_nxt;
}edge[MAXN],pos_[MAXN];
inline void addedge(int u,int v,int w)
{
    edge[++cnt].v = v;
    edge[cnt]._nxt = ori_[u];
    edge[cnt].w = w;
    ori_[u] = cnt;
}
inline void add(int u,int v,int w) {addedge(u,v,w),addedge(v,u,0);}
set<int> pany;
bool able[MAXN],pr[MAXN];
namespace Dinitz
{
    const int inf = 0x7f7f7f7f;
    int depth[MAXN],fire[MAXN];
    inline bool Bfs(int s,int t)
    {
        memset(depth,-1,sizeof(depth));
        queue<int> q;
        q.push(s),depth[s] = 0;
        while(!q.empty())
        {
            int v,tp = q.front();q.pop();
            for(reg e = ori_[tp];e;e = edge[e]._nxt)
                if(depth[v = edge[e].v] == -1&&(edge[e].w&&able[tp]))
                {
                    depth[v] = depth[tp] + 1,q.push(v);
                    if(edge[e].w >= 50) able[v] = 1;
                }
        }
        return (depth[t] != -1);
    }
    inline int dfs(int x,int t,int _flow)
    {
        if(x == t) return _flow; int v,flow_ = 0;
        for(reg e = fire[x];e;e = edge[e]._nxt)
        {
            fire[x] = e;
            if(depth[v = edge[e].v] == depth[x] + 1&&(edge[e].w&&able[x]))
            {
                if(edge[e].w >= 50) able[v] = 1;
                int flow = dfs(v,t,min(_flow,edge[e].w));
                _flow -= flow,flow_ += flow;
                edge[e].w -= flow,edge[e ^ 1].w += flow;
                if(!_flow) break;
            }
        }
        if(!flow_) depth[x] = -1;
        return flow_;
    }
    inline int Dinic(int s,int t)
    {
        int ans = 0;
        while(Bfs(s,t))
        {
            for(set<int>::iterator i = pany.begin();i != pany.end();i++) fire[*i] = ori_[*i];
            ans += dfs(s,t,inf);
        }
        return ans;
    }
}
int main()
{
    cnt = 1,n = Read(1);
    for(reg i = 1;i <= n;i++)
    {
        int u = Read(1),v = Read(1),w = Read(1);
        add(u,v,w);
        pany.insert(u),pany.insert(v);
    }
    for(reg i = 1;i <= cnt;i++) pos_[i] = edge[i];
    for(set<int>::iterator i = pany.begin();i != pany.end();i++)
    {
        memset(able,0,sizeof(able));
        memset(pr,0,sizeof(pr));
        set<int> pr_;
        able[*i] = 1;
        int num = 1;
        while(num)
        {
            num = 0;
            for(set<int>::iterator j = pany.begin();j != pany.end();j++)
            {
                if(*i == *j||pr[*j]) continue;
                int max_ = Dinitz::Dinic(*i,*j);
                for(reg k = 1;k <= cnt;k++) edge[k] = pos_[k];
                if(max_ >= 50) pr_.insert(*j),num++,pr[*j] = able[*j] = 1;
            }
        }
        for(set<int>::iterator j = pr_.begin();j != pr_.end();j++) printf("%d %d\n",*i,*j);
    }
    return 0;
}