[网络流24题] 魔术球问题



  • 每日热手题系列
    跟最小路径覆盖差不多吧……总觉得输出方案做得很不优美,尤其是用了自己的老板子以后

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 16384, MAX_NODE = 262144;
    #define reset(x) memset(x,0,sizeof x)
    template <class T> class Graph_Maxflow_Dinic
    {
    public:
        T tInfinity;
        struct edge
        {
            int p, o;
            T c;
        };
        int s, t;
        T ans=0, tans;
        T dis[MAX_NODE];
        vector <edge> g[MAX_NODE];
        Graph_Maxflow_Dinic()
        {
            tInfinity = 1e+9;
        }
        void make(int p, int q, T c)
        {
            int sz1 = g[p].size(), sz2 = g[q].size();
            edge tmp;
            tmp.p = q;
            tmp.c = c;
            tmp.o = sz2;
            g[p].push_back(tmp);
            tmp.p = p;
            tmp.c = 0;
            tmp.o = sz1;
            g[q].push_back(tmp);
        }
        void reset_graph(int maxnode)
        {
            for (int i = 0; i <= maxnode; i++)
                g[i].clear();
        }
        int dinic_bfs()
        {
            queue<int> q;
            q.push(s);
            memset(dis, 0xff, sizeof dis);
            dis[s] = 1;
            while (q.size())
            {
                int p = q.front();
                q.pop();
                for (int i = 0; i < g[p].size(); i++)
                    if (g[p][i].c > 0 && dis[g[p][i].p] < 0)
                        q.push(g[p][i].p),
                               dis[g[p][i].p] = dis[p] + 1;
            }
            return dis[t] > 0;
        }
        T dinic_dfs(int p, T lim)
        {
            T flow = 0;
            if (p == t)
                return lim;
            for (int i = 0; i < g[p].size(); i++)
            {
                if (g[p][i].c > 0 && dis[g[p][i].p] == dis[p] + 1)
                {
                    T tmp = dinic_dfs(g[p][i].p, min(lim, g[p][i].c));
                    if (tmp > 0)
                    {
                        g[p][i].c -= tmp;
                        g[g[p][i].p][g[p][i].o].c += tmp;
                        flow += tmp;
                        lim -= tmp;
                    }
                }
            }
            return flow;
        }
        T solve(int src, int tar)
        {
            s = src;
            t = tar;
            tans = 0;
            while (dinic_bfs())
            {
                while (tans = dinic_dfs(s, tInfinity))
                {
                    ans += tans;
                }
            }
            return ans;
        }
    };
    
    Graph_Maxflow_Dinic <int> g;
    
    int n,t1,t2,t3,t4;
    
    int check(int p,int q)
    {
        int t=sqrt(p+q);
        if(t*t==p+q)
            return 1;
        else
            return 0;
    }
    
    vector <int> mat[N];
    int vis[N];
    
    int main()
    {
        cin>>n;
        for(int i=1; i<=n*n*2; i++)
        {
            g.make(1,2*i+1,1);
            g.make(2*i+2,2,1);
            for(int j=1; j<i; j++)
                if(check(i,j))
                    g.make(2*i+1,2*j+2,1);
            g.solve(1,2);
            if(i-g.ans > n)
            {
                cout<<i-1<<endl;
                for(int j=0; j<g.g[1].size(); j++)
                {
                    int p=g.g[1][j].p;
                    for(int k=0; k<g.g[p].size(); k++)
                    {
                        if(g.g[p][k].c==0 && g.g[p][k].p>2)
                        {
                            mat[(p-1)/2].push_back((g.g[p][k].p-1)/2);
                            mat[(g.g[p][k].p-1)/2].push_back((p-1)/2);
                        }
                    }
                }
                for(int j=1; j<i; j++)
                {
                    if(mat[j].size()==1)
                    {
                        cout<<j;
                        vis[j]=1;
                        int p=mat[j][0];
                        mat[j].clear();
                        while(mat[p].size()==2)
                        {
                            vis[p]=1;
                            int tmp=p;
                            cout<<" "<<p;
                            if(mat[p][0]==0||mat[mat[p][0]].size()==0)
                                p=mat[p][1];
                            else
                                p=mat[p][0];
                            mat[tmp].clear();
                        }
                        vis[p]=1;
                        cout<<" "<<p;
                        mat[p].clear();
                        cout<<endl;
                    }
                }
                for(int j=1; j<i; j++)
                    if(!vis[j])
                        cout<<j<<endl;
    
                return 0;
            }
        }
    }
    

    来自:https://www.cnblogs.com/mollnn/p/11724877.html


Log in to reply
 

最新帖子

推荐阅读