(luogu2765)魔术球问题

发表于 | 分类于 ， ，

一道神奇的网络流(二分图)题目

思路:

考虑往柱子上一个个加球, 这样就只需考虑每个球与之前的球的关系

对于放进去的球, 有两种方案:

1. 单独放在一个柱子上

2.放在一个球的后面

如果选择方案2, 放进去的球只能放在一个球后面, 我们可以尝试使用二分图匹配解决

将一个球分割为两个点u和u’, 所有的u结点为X集合, u’结点为Y集合

如果球v可以放在u的后面, 则连一条边<u,v’>

每加入一个球重新构图, 求最大匹配, 如果匹配数没有增加, 则加一个柱子, 直到不能再加为止, 则答案为加入球数-1(因为最后一个球不能加进去)

输出的话, 建一个数组, 表示某个球的下一个球, 如果匹配数增加则刷新该数组(防止最后那个不能添加的球干扰输出)

代码:

使用网络流求解二分图匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <queue>
using namespace std;
const int Mn(10050),Mm(100050);
inline int _min(int x,int y) { return x<y ? x : y; }
struct edge	//边表
{
    int s,e,cp,nt; //起点,终点,可改变量,下一条边
}ed[Mm<<1];
int vs[Mn],ec(-1);
void adde(int s,int e)	//加边
{
    ed[++ec].s=s, ed[ec].e=e, ed[ec].cp=1; ed[ec].nt=vs[s];
    vs[s]=ec;
    ed[++ec].s=e, ed[ec].e=s, ed[ec].cp=0; ed[ec].nt=vs[e];
    vs[e]=ec;
}
//起点为0终点为1
//dinic
int d[Mn],p[Mn];
bool bfs()
{
    memset(d,0,sizeof d);
    queue<int> q;
    q.push(0);
    d[0] = 1;
    while(!q.empty())
    {
        int x(q.front()); q.pop();
        for(int i(vs[x]);i!=-1;i=ed[i].nt)
        {
            edge& e(ed[i]);
            if(!d[e.e] && e.cp)
            {
                d[e.e] = d[x]+1;
                q.push(e.e);
            }
        }
    }
    return d[1];
}
int dnc(int x,int a)
{
    if(x==1 || a==0)    return a;
    int ret(0);
    for(int& i(p[x]);i!=-1;i=ed[i].nt)
    {
        edge& e(ed[i]);
        int f;
        if(d[e.e]==d[x]+1 && (f = dnc(e.e, _min(a, e.cp))) > 0)
        {
            e.cp -= f;
            ed[i^1].cp += f;
            ret += f;
            a -= f;
            if(a==0)    break;
        }
    }
    return ret;
}
int nxt[Mn];	//输出所用数组
bool isv[Mn];	//是否已经输出
void prtans(int x)	//递归输出
{
    isv[x] = true;
    printf("%d ",x);
    if(nxt[x])  prtans(nxt[x]);
}
int main()
{
    memset(vs,-1,sizeof vs);
    int n; cin >> n;
    int col(0),bal(0);	//柱子数,球数
    while(true)
    {
        ++bal;
        adde(0,bal*2); adde(bal*2+1,1);	//u编号为2n,u'编号为2n+1
        for(int i(1),j(1);;i+=2*j+1,++j)	//建二分图
        {
            if(i<=bal)  continue;
            if(i>=2*bal)    break;
            adde(2*(i-bal),bal*2+1);
        }
        int flw(0);	//匹配数增量(即增广量)
        while(bfs())
        {
            memcpy(p,vs,sizeof p);
            flw += dnc(0,INT_MAX);
        }
        if(!flw)    ++col;	//如果无法放入球,柱子数+1
        else	//刷新输出数组
        {
            for(int i(2);i<=bal*2;i+=2)
                for(int j(vs[i]);j!=-1;j=ed[j].nt)
                    if(!ed[j].cp && ed[j].e>1)
                    { nxt[i/2] = ed[j].e/2; break; }
        }
        if(col>n)   break;	//如果柱子数超出限制, 停止
    }
    //输出
    cout << bal-1;
    for(int i(1);i<bal;++i)
        if(!isv[i])
        { cout << endl; prtans(i); }
    return 0;
}