【纪中】Day10+

【C】
题意:求无向图中两点之间的路径数。
水题。由于每个点只在一个简单环上,所以缩点以后图就变成一颗树了,而只要进过一个环,就有两条路。
于是用tarjin缩点再跑lca即可。缩点也可以用dfs,写完tarjin结果忘了无向图怎么处理,只好改dfs。。。
【棋盘游戏】
题意:从一个点走到(0,0),一步可往左、下、左下三个方向走任意步,询问先手的输赢情况。
明显的博弈论,正解是威佐夫博弈,公式很简单:
记w=(int)[((sqrt(5)+1)/2)*z ];
若w=x,则先手必败,否则先手必胜。
来讲讲部分分的做法。
30%:显然,若起点为(0,0)则先手必输,那么,从(0,0)右、上、右上的点便是先手必胜。接着,从(0,0)开始一层一层地找,若没有被标记过先手必胜,则就是先手必败。
60%:既然可以从上述方法得知输赢情况,那么,可以发现先手必败的情况特别少,打表发现,每一个必败点(x, y),(x - 1)(y - 2)、(x - 2)(y - 3)其中一个一定是必败点,可以找规律求解(反正我没找到)。
【偷窃】
题意:在一堆正方体中拿走最多的数量,并且使其三视图不改变。
正解是二分图匹配,对于行和列的最高点建边,再分别连向源点和汇点,流量是其最大值的数值,跑网络流求最大匹配。
但是,水水就能过去的题为什么要打网络流。要使三视图不改变,只要最高的不少,其余的全搬走只剩一个即可。那么,对于列上的最大值,去找行上有没有与其想等的,如果有,在一个位置就可满足行列的要求,如果没有,就随便找一个比它大的放。
代码如下:
继续阅读【纪中】Day10+

Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

继续阅读Day1:A+组

网络流/费用流

【流模型】
如同我们可以把一个实际的道路地图抽象成一个有向图来计算两点之间的最短路径,我们也可以将一个有向图看作一个网流络来解决另一类型的问题。网络流比较适合用来模拟液体流经管道、 电流在电路网络中的运动、 信息网络中信息的传递等等类似的过程。
我们可以将网络流类比成水流, 如下图给出一个有向图 G =(V, E).图中的边可以想象成管道, 顶点则是管道的连接点。 边上的权值我们称之为这条边的流量上限, 可以把它想象成这条管道能通过的水流的多少。 对于图中每条边e我们记它的流量上限为 c(e) .

【最大流模型】
对于有源点s和汇点t的图,则称为网络流图。在这样的图中,源点入度为 0 且可以产生无穷大的流量,汇点出度为 0 且可以吸
收无穷大的流量。
称一条从源点到汇点的,并使除源汇之外所有结点满足流量平衡,所有边满足流量约束的流方案为有源汇网络的可行流。(这里的流方案并不一定只沿一条路流,也可能在多个结点上出现支路,但要保证满足流量约束与流量平衡条件。)
最大的可行流方案为最大流。求解最大流的问题称为最大流问题。

【求解最大流/Dinic算法】
Dinic 算法的主要思想就是每次寻找最短的增广路,并沿着它增广。因为最短增广路的长度在增广过程中始终不会变短,所以无需每次都通过广搜来寻找最短增广路。我们可以先进行一次广搜,然后考虑由近距离顶点指向远距离顶点的边所组成的分层图,在上面进行深搜寻找最短增广路(这里一次深搜就可以完成多次增广的工作)。每增广一条边,就要在其反向边上加上流入的流量,在这条边上减去流入的流量,这样,在找到一条更优的增广路后,便可以直接从反向边进行修改。
如果在分层图上找不到新的增广路了(此时我们得到了分层图所对应的阻塞流),则说明最短增广路的长度变长了或不存在增广路了,于是重新构造新的分层图。
注: 建边时一般从2开始建,这样便于正、反边的互换,只要(^1)便能得到另一条边。
构建分层图的代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q;

int bfs()  {
    int v, now;
    for (int i = s;i <= t; i++) cnt[i] = en[i], dir[i] = -1;
    dir[s] = 0;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())  {
        for (int e = en[now = q.front()]; e ; e = next[e])
            if (val[e] > 0 && dir[v = gt[e]] == -1)  {
                dir[v] = dir[now] + 1;
                q.push(v);
                if (v == t) return 1;
            }
        q.pop();
    }
    return 0;
}

Dinic代码:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Dinic(int u, int flow)  {
    if (u == t) return flow;
    int acc = 0, v, del;
    for (int &e = cnt[u]; e ; e = next[e])  
        if (val[e] > 0 && dir[u] + 1 == dir[v = gt[e]] && dir[v] > 0)  {
            del = Dinic(v, min(val[e], flow - acc));
            if (del)  {
                val[e] -= del;
                val[e ^ 1] += del;
                acc += del;
                if (acc == flow) break;
            }
        }
    if (acc != flow) dir[u] = -1;
    return acc;
}

【费用流】
费用流则是在网络流的基础上给每条边多加了个属性,即单位流量的费用,一般在费用流的可行方案中,要求费用与流量平衡。
注意到,在网络流的求解中,每次都是随便选取一条边来进行增广,费用流中由于边多了一个权值,选边的顺序就需要确定了。显而易见,可以贪心地在残余网络上选最小费用的路径进行增广。多了个权值,在建边时反向边的权值便是负值,所以不能Dijkstra来求最小值,要用队列优化的 Bellman-Ford 算法。
实际上,费用流与网络流的差别也就在选取边的顺序上;


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
queue<int> q;

int spfa()  {
    memset(vis, 0, sizeof vis);
    for (int i = 1;i <= 2 * N; i++) dir[i] = INF;
    int nxt, now;
    dir[s] = 0;
    q.push(s);
    vis[s] = 1;
    while (!q.empty())  {
        vis[now = q.front()] = 0;
        for (int e = beg[now]; e ;e = next[e])
            if (cap[e] > 0 && dir[now] + cost[e] < dir[nxt = gt[e]])  {
                dir[nxt] = dir[now] + cost[e];
                if (!vis[nxt])  {
                    vis[nxt] = 1;
                    q.push(nxt);
                }
            }
            q.pop();
    }
    if (dir[t] < INF) return 1;
    return 0;
}

【网络流题目】(两题代码相同)

【POJ】2186Popular Cows

【QZYZ】1238草地排水

继续阅读网络流/费用流