JulyRina's blog
welcome to July Rina's blog
posts - 22,comments - 1,trackbacks - 0

题目

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

基本思路

这个问题非常类似于01背包问题,所不同的是每种物品有无限件。也就是从每种物品的角度考虑,与它相关的策略已并非取或不取两种,而是有取0件、取1件、取2件……等很多种。如果仍然按照解01背包时的思路,令f[i][v]表示前i种物品恰放入一个容量为v的背包的最大权值。仍然可以按照每种物品不同的策略写出状态转移方程,像这样:

f[i][v]=max{f[i-1][v-k*c[i]]+k*w[i]|0<=k*c[i]<=v}

这跟01背包问题一样有O(VN)个状态需要求解,但求解每个状态的时间已经不是常数了,求解状态f[i][v]的时间是O(v/c[i]),总的复杂度可以认为是O(V*Σ(V/c[i])),是比较大的。

将01背包问题的基本思路加以改进,得到了这样一个清晰的方法。这说明01背包问题的方程的确是很重要,可以推及其它类型的背包问题。但我们还是试图改进这个复杂度。

一个简单有效的优化

完全背包问题有一个很简单有效的优化,是这样的:若两件物品i、j满足c[i]<=c[j]且w[i]>=w[j],则将物品j去掉,不用考虑。这个优化的正确性显然:任何情况下都可将价值小费用高得j换成物美价廉的i,得到至少不会更差的方案。对于随机生成的数据,这个方法往往会大大减少物品的件数,从而加快速度。然而这个并不能改善最坏情况的复杂度,因为有可能特别设计的数据可以一件物品也去不掉。

这个优化可以简单的O(N^2)地实现,一般都可以承受。另外,针对背包问题而言,比较不错的一种方法是:首先将费用大于V的物品去掉,然后使用类似计数排序的做法,计算出费用相同的物品中价值最高的是哪个,可以O(V+N)地完成这个优化。这个不太重要的过程就不给出伪代码了,希望你能独立思考写出伪代码或程序。

转化为01背包问题求解

既然01背包问题是最基本的背包问题,那么我们可以考虑把完全背包问题转化为01背包问题来解。最简单的想法是,考虑到第i种物品最多选V/c[i]件,于是可以把第i种物品转化为V/c[i]件费用及价值均不变的物品,然后求解这个01背包问题。这样完全没有改进基本思路的时间复杂度,但这毕竟给了我们将完全背包问题转化为01背包问题的思路:将一种物品拆成多件物品。

更高效的转化方法是:把第i种物品拆成费用为c[i]*2^k、价值为w[i]*2^k的若干件物品,其中k满足c[i]*2^k<=V。这是二进制的思想,因为不管最优策略选几件第i种物品,总可以表示成若干个2^k件物品的和。这样把每种物品拆成O(log V/c[i])件物品,是一个很大的改进。

但我们有更优的O(VN)的算法。

O(VN)的算法

这个算法使用一维数组,先看伪代码:

for i=1..N     
   for v=0..V
      f[v]=max{f[v],f[v-cost]+weight}

你会发现,这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]],所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

值得一提的是,上面的伪代码中两层for循环的次序可以颠倒。这个结论有可能会带来算法时间常数上的优化。

这个算法也可以以另外的思路得出。例如,将基本思路中求解f[i][v-c[i]]的状态转移方程显式地写出来,代入原方程中,会发现该方程可以等价地变形成这种形式:

f[i][v]=max{f[i-1][v],f[i][v-c[i]]+w[i]}

将这个方程用一维数组实现,便得到了上面的伪代码。

最后抽象出处理一件完全背包类物品的过程伪代码:

procedure CompletePack(cost,weight)     
   for v=cost..V
      f[v]=max{f[v],f[v-c[i]]+w[i]}

总结

完全背包问题也是一个相当基础的背包问题,它有两个状态转移方程,分别在“基本思路”以及“O(VN)的算法“的小节中给出。希望你能够对这两个状态转移方程都仔细地体会,不仅记住,也要弄明白它们是怎么得出来的,最好能够自己想一种得到这些方程的方法。事实上,对每一道动态规划题目都思考其方程的意义以及如何得来,是加深对动态规划的理解、提高动态规划功力的好方法。

posted @ 2015-02-18 20:31 JulyRina 阅读(227) | 评论 (0)编辑 收藏

题目

有N件物品和一个容量为V的背包。第i件物品的费用是c[i],价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题,特点是:每种物品仅有一件,可以选择放或不放。

用子问题定义状态:即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是:

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

这个方程非常重要,基本上所有跟背包相关的问题的方程都是由它衍生出来的。所以有必要将它详细解释一下:“将前i件物品放入容量为v的背包中”这个子问题,若只考虑第i件物品的策略(放或不放),那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品,那么问题就转化为“前i-1件物品放入容量为v的背包中”,价值为f[i-1][v];如果放第i件物品,那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”,此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。

优化空间复杂度

以上方法的时间和空间复杂度均为O(VN),其中时间复杂度应该已经不能再优化了,但空间复杂度却可以优化到O。

先考虑上面讲的基本思路如何实现,肯定是有一个主循环i=1..N,每次算出来二维数组f[i][0..V]的所有值。那么,如果只用一个数组f[0..V],能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢?f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来,能否保证在推f[i][v]时(也即在第i次主循环中推f[v]时)能够得到f[i-1][v]和f[i-1][v-c[i]]的值呢?事实上,这要求在每次主循环中我们以v=V..0的顺序推f[v],这样才能保证推f[v]时f[v-c[i]]保存的是状态f[i-1][v-c[i]]的值。伪代码如下:

for i=1..N     
   for v=V..0
      f[v]=max{f[v],f[v-c[i]]+w[i]};

其中的f[v]=max{f[v],f[v-c[i]]}一句恰就相当于我们的转移方程f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]},因为现在的f[v-c[i]]就相当于原来的f[i-1][v-c[i]]。如果将v的循环顺序从上面的逆序改成顺序的话,那么则成了f[i][v]由f[i][v-c[i]]推知,与本题意不符,但它却是另一个重要的背包问题P02最简捷的解决方案,故学习只用一维数组解01背包问题是十分必要的。

事实上,使用一维数组解01背包的程序在后面会被多次用到,所以这里抽象出一个处理一件01背包中的物品过程,以后的代码中直接调用不加说明。

过程ZeroOnePack,表示处理一件01背包中的物品,两个参数cost、weight分别表明这件物品的费用和价值。

procedure ZeroOnePack(cost,weight)     
   for v=V..cost
      f[v]=max{f[v],f[v-cost]+weight}

注意这个过程里的处理与前面给出的伪代码有所不同。前面的示例程序写成v=V..0是为了在程序中体现每个状态都按照方程求解了,避免不必要的思维复杂度。而这里既然已经抽象成看作黑箱的过程了,就可以加入优化。费用为cost的物品不会影响状态f[0..cost-1],这是显然的。

有了这个过程以后,01背包问题的伪代码就可以这样写:

for i=1..N     
   ZeroOnePack(c[i],w[i]);

初始化的细节问题

我们看到的求最优解的背包问题题目中,事实上有两种不太相同的问法。有的题目要求“恰好装满背包”时的最优解,有的题目则并没有要求必须把背包装满。一种区别这两种问法的实现方法是在初始化的时候有所不同。

如果是第一种问法,要求恰好装满背包,那么在初始化时除了f[0]为0其它f[1..V]均设为-∞,这样就可以保证最终得到的f[N]是一种恰好装满背包的最优解。

如果并没有要求必须把背包装满,而是只希望价格尽量大,初始化时应该将f[0..V]全部设为0。

为什么呢?可以这样理解:初始化的f数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满,那么此时只有容量为0的背包可能被价值为0的nothing“恰好装满”,其它容量的背包均没有合法的解,属于未定义的状态,它们的值就都应该是-∞了。如果背包并非必须被装满,那么任何容量的背包都有一个合法解“什么都不装”,这个解的价值为0,所以初始时状态的值也就全部为0了。

这个小技巧完全可以推广到其它类型的背包问题,后面也就不再对进行状态转移之前的初始化进行讲解。

一个常数优化

前面的伪代码中有 for v=V..1,可以将这个循环的下限进行改进。

由于只需要最后f[v]的值,倒推前一个物品,其实只要知道f[v-w[n]]即可。以此类推,对以第j个背包,其实只需要知道到f[v-sum{w[j..n]}]即可,即代码中的

for i=1..N     
   for v=V..0

可以改成

for i=1..n     
   bound=max{V-sum{w[i..n]},c[i]}
   for v=V..bound

这对于V比较大时是有用的。

小结

01背包问题是最基本的背包问题,它包含了背包问题中设计状态、方程的最基本思想,另外,别的类型的背包问题往往也可以转换成01背包问题求解。故一定要仔细体会上面基本思路的得出方法,状态转移方程的意义,以及最后怎样优化的空间复杂度。

posted @ 2015-02-18 20:30 JulyRina 阅读(110) | 评论 (0)编辑 收藏
题目大意:求图上单点到单点之间的最短路。
题目分析:SPFA(Shortest Path Faster Algorithm)是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算。
算法大致流程是用一个队列来进行维护。 初始时将源加入队列。 每次从队列中取出一个元素,并对所有与他相邻的点进行松弛,若某个相邻的点松弛成功,则将其入队。 直到队列为空时算法结束。
这个算法,简单的说就是队列优化的bellman-ford,利用了每个点不会更新次数太多的特点发明的此算法
SPFA——Shortest Path Faster Algorithm,它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径,可以处理负边。SPFA的实现甚至比Dijkstra或者Bellman_Ford还要简单:
设Dist代表S到I点的当前最短距离,Fa代表S到I的当前最短路径中I点之前的一个点的编号。开始时Dist全部为+∞,只有Dist[S]=0,Fa全部为0。
维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个点S。用一个布尔数组记录每个点是否处在队列中。
每次迭代,取出队头的点v,依次枚举从v出发的边v->u,设边的长度为len,判断Dist[v]+len是否小于Dist[u],若小于则改进Dist[u],将Fa[u]记为v,并且由于S到u的最短距离变小了,有可能u可以改进其它的点,所以若u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是S到所有的最短距离都确定下来,结束算法。若一个点入队次数超过n,则有负权环。
SPFA 在形式上和宽度优先搜索非常类似,不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列,但是SPFA中一个点可能在出队列之后再次被放入队列,也就是一个点改进过其它的点之后,过了一段时间可能本身被改进,于是再次用来改进其它的点,这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k,有办法证明对于通常的情况,k在2左右。
SPFA算法(Shortest Path Faster Algorithm),也是求解单源最短路径问题的一种算法,用来解决:给定一个加权有向图G和源点s,对于图G中的任意一点v,求从s到v的最短路径。 SPFA算法是Bellman-Ford算法的一种队列实现,减少了不必要的冗余计算,他的基本算法和Bellman-Ford一样,并且用如下的方法改进: 1、第二步,不是枚举所有节点,而是通过队列来进行优化 设立一个先进先出的队列用来保存待优化的结点,优化时每次取出队首结点u,并且用u点当前的最短路径估计值对离开u点所指向的结点v进行松弛操作,如果v点的最短路径估计值有所调整,且v点不在当前的队列中,就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。 2、同时除了通过判断队列是否为空来结束循环,还可以通过下面的方法: 判断有无负环:如果某个点进入队列的次数超过V次则存在负环(SPFA无法处理带负环的图)。
SPFA算法有两个优化算法 SLF 和 LLL: SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j)<dist(i),则将j插入队首,否则插入队尾。 LLL:Large Label Last 策略,设队首元素为i,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。 SLF 可使速度提高 15 ~ 20%;SLF + LLL 可提高约 50%。 在实际的应用中SPFA的算法时间效率不是很稳定,为了避免最坏情况的出现,通常使用效率更加稳定的Dijkstra算法。
#include <cstdio>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;

typedef pair<intint> P;
vector<P> G[maxn];
queue<int> que;
int V, E, dist[maxn];
bool vis[maxn];

void spfa(int s) {
    fill(dist, dist+V, INF);
    fill(vis, vis+V, false);
    dist[s] = 0;
    while(!que.empty()) que.pop();
    que.push(s);
    while(!que.empty()) {
        int u = que.front();
        que.pop();
        vis[u] = false;
        int sz = G[u].size();
        for(int i=0;i<sz;i++) {
            int v = G[u][i].first;
            int w = G[u][i].second;
            if(dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if(!vis[v]) {
                    vis[v] = true;
                    que.push(v);
                }
            }
        }
    }
}

int main() {
    scanf("%d%d" , &E, &V);
    for(int i=0;i<V;i++) G[i].clear();
    for(int i=0;i<E;i++) {
        int u, v, w;
        scanf("%d%d%d" , &u, &v, &w);
        u --; v --;
        G[u].push_back(make_pair(v, w));
        G[v].push_back(make_pair(u, w));
    }
    spfa(0);
    printf("%d\n", dist[V-1]);
    return 0;
}
posted @ 2015-02-13 19:42 JulyRina 阅读(135) | 评论 (0)编辑 收藏
题目大意:求图上单点到单点之间的最短路。
题目分析:之前我们在同一道问题上分析过了单源最短路问题的Dijkstra算法
使用邻接矩阵实现的Dijkstra算法的时间复杂度是O(|V|^2)。使用邻接表的话,更新最短距离只需要更新每一条边即可,因此这部分的时间复杂度是O(|E|)。但是每次要枚举所有的顶点来查找下一个使用的顶点,因此最终复杂度还是O(|V|^2)。在|E|比较小时,大部分经历放在了查找下一次要是用的顶点上,因此需要使用合适的数据结构对其进行优化。
需要优化的是数值的插入(更新)和取出最小值两个操作,因此使用堆就可以了。把每个顶点当前的最短距离用堆维护,在更新最短距离时,把对应的元素往根的方向移动以满足堆的性质。而每次从堆中取出的最小值就是下一次要使用的顶点。这样堆中元素共有O(|V|)个,更新和取出数值的操作有O(|E|)次,因此整个算法的复杂度是O(|E|log(V))
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;

typedef pair<intint> P; //first是最短距离,second是顶点的编号
int V, dist[maxn];
vector<P> G[maxn];

void dijkstra(int s) {
    //通过指定greater<P>参数,堆按照first从小到大的顺序取出值
    priority_queue<P, vector<P>, greater<P> > que;
    fill(dist, dist + V , INF);
    dist[s] = 0;
    while(!que.empty()) que.pop();
    que.push(P(0, s));
    while(!que.empty()) {
        P p = que.top(); que.pop();
        int u = p.second;
        if(dist[u] < p.first) continue;
        int sz = G[u].size();
        for(int i=0;i<sz;i++) {
            int to = G[u][i].second;
            int cost = G[u][i].first;
            if(dist[to] > dist[u] + cost) {
                dist[to] = dist[u] + cost;
                que.push(P(dist[to], to));
            }
        }
    }
}

int main() {
    int m;
    scanf("%d%d" , &m, &V);
    for(int i=0;i<V;i++) G[i].clear();
    for(int i=0;i<m;i++) {
        int from, to, cost;
        scanf("%d%d%d" , &from, &to, &cost);
        from --; to --;
        G[from].push_back(P(cost, to));
        G[to].push_back(P(cost, from));
    }
    dijkstra(0);
    printf("%d\n", dist[V-1]);
    return 0;
}
posted @ 2015-02-13 19:38 JulyRina 阅读(121) | 评论 (0)编辑 收藏
题目大意:求图上单点到单点之间的最短路。

题目分析:让我们考虑没有负边的情况。在Bellman-Ford算法中,如果dist[i]还不是最短距离的话,那么即使进行dist[j]=dist[i]+(从i到j的边的权值)的更新,dist[j]也不会变成最短距离。而且,即使dist[i]没有变化,每一次循环也要检查一遍从i出发的所有变。这显然是很浪费时间的。因此可以对算法作如下修改。
(1)找到最短距离已经确定的顶点,从他出发更新相邻顶点的最短距离。
(2)此后不再需要关心(1)中的“最短距离已经确定的顶点”。
在(1)和(2)中提到的“最短距离已经确定的”要怎么得到时问题的关键。在最开始时,只有起点的最短距离是确定的。而在尚未使用过的顶点中,距离dist[i]最小的顶点就会加入“最短距离已经确定的顶点”的阵营。这是因为由于不会存在负边,所以dist[i]不会在之后的更新中变小。这个算法叫做Dijkstra算法。
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010;

typedef pair<intint> P;
vector<P> G[maxn];
int V, E, dist[maxn];
bool vis[maxn];

void dijkstra(int s) {
    fill(dist, dist + V, INF);
    fill(vis, vis + V, false);
    dist[s] = 0;
    while(true) {
        int u = -1;
        for(int i=0;i<V;i++)
            if(!vis[i] && (u == -1 || dist[i] < dist[u]))
                u = i;
        if(u == -1) break;
        vis[u] = true;
        int sz = G[u].size();
        for(int i=0;i<sz;i++) {
            int v = G[u][i].first;
            int w = G[u][i].second;
            dist[v] = min(dist[v], dist[u] + w);
        }
    }
}

int main() {
    scanf("%d%d" , &E, &V);
    for(int i=0;i<V;i++) G[i].clear();
    for(int i=0;i<E;i++) {
        int u, v, w;
        scanf("%d%d%d" , &u, &v, &w);
        u --; v --;
        G[u].push_back(make_pair(v, w));
        G[v].push_back(make_pair(u, w));
    }
    dijkstra(0);
    printf("%d\n", dist[V-1]);
    return 0;
}
posted @ 2015-02-13 19:34 JulyRina 阅读(201) | 评论 (0)编辑 收藏
题目大意:求图上单点到单点之间的最短路。

题目分析:单源最短路问题是固定一个起点,求它到其他所有点的最短路的问题。终点也固定问题叫做两点之间最短路问题。但是因为单源最短路问题的复杂度是一样的,因此通常当作单源最短路问题来求解。
记从起点s出发到顶点i的最短距离为dist[i]。则下述等式成立。
dist[i] = min{dist[j]+(从j到i的边的权值)|e=(j,i)∈E}
如果给定的图是一个DAG,就可以按托不许给顶点编号,并利用这条递推关系计算出dist。但是,如果图中有圈,就无法利用这样的关系进行计算。
在这种情况下,记当前到顶点i的最短距离为dist[i],并设初值dist[s]=0,dist[i]=INF(足够大的常数),再不断使用这条地推关系式更新dist值,就可以算出新的dist。
只要途中不存在负圈,这样的更新操作就是有限的。结束之后的最短操作就是所求的最短距离了。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define INF (1<<29)
const int maxn = 1010, maxm = 4040;

int n, m;

struct Edge { int from, to, cost; } edge[maxm];
int V, E, dist[maxn];

void bellman_ford(int s) {
    for(int i=0;i<V;i++) dist[i] = INF;
    dist[s] = 0;
    while(true) {
        bool update = false;
        for(int i=0;i<E;i++) {
            Edge e = edge[i];
            if(dist[e.from] != INF && dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                update = true;
            }
        }
        if(!update) break;
    }
}

int main() {
    scanf("%d%d" , &m, &n);
    V = n; E = 2 * m;
    for(int i=0;i<E;i+=2) {
        Edge e;
        int from, to, cost;
        scanf("%d%d%d" , &from, &to, &cost);
        from --; to --;
        edge[i].from = from;
        edge[i].to = to;
        edge[i].cost = cost;
        edge[i+1].from = to;
        edge[i+1].to = from;
        edge[i+1].cost = cost;
    }
    bellman_ford(0);
    printf("%d", dist[n-1]);
    return 0;
}
这个算法叫做Bellman-Ford算法。如果在图中不存在从s可达的负圈,那么最短路不会经过同一个顶点两次(也就是说,最多通过|V|-1次),while(true)的循环最多经过|V|-1次,因此,复杂度是O(VE)。反之,如果存在从s可达的负圈,那么在第|V|次循环中也会更新dist的值,因此也可以用这个性质来检查负圈。如果一开始对所有的i,都把dist[i]设为0,那么可以检查出所有的负圈。
bool find_negetive_loop() {
    memset(dist, 0, sizeof(dist));
    
    for(int i=0;i<V;i++) {
        for(int j=0;j<E;j++) {
            if(dist[e.to] > dist[e.from] + e.cost) {
                dist[e.to] = dist[e.from] + e.cost;
                if(i == V-1) return true;
            }
        }
    }
    return false;
}
posted @ 2015-02-13 19:32 JulyRina 阅读(140) | 评论 (0)编辑 收藏
题目大意:有N(N<100,000)个人要去M(M<10)个星球,每个人只可以去一些星球,一个星球最多容纳Ki个人。请问是否所有人都可以选择自己的星球
题目分析;直接建立二分图模型,使用匈牙利算法。
    匈牙利算法可以解决多重匹配,原理和二分图最大匹配很像。注意不要把可以匹配多个的点分割然后按照正常的二分匹配来做,那样肯定会挂的。
    解决多重匹配就是记录一下多重匹配的点(简称Y方点)已经匹配了Pi个点。如果Pi<Ki那么就直接上了,否则的话继续搜索Yi已经匹配的每一个点并将Yi染色。
    因为Yi搜一次就需要染色了,而且Y方点最多是10个,所以每次找增广路的深度最多是10,这样就很快了。
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;

const int maxn = 100010;
const int maxm = 11;
int y_match[maxn][maxm], g[maxn][maxm], cnt[maxm], capacity[maxn], n, m;
bool vis[maxm];

bool dfs(int x) {
    for(int i=0;i<m;i++) {
        if(g[x][i] == 0 || vis[i] == truecontinue;
        vis[i] = true;
        if(cnt[i] < capacity[i]) {
            y_match[x][cnt[i]++] = x;
            return true;
        } else {
            for(int j=0;j<capacity[i];j++) {
                if(dfs(y_match[i][j]) == true) {
                    y_match[i][j] = x;
                    return true;
                }
            }
        }
    }
    return false;
}
bool hungary(int n) {
    for(int i=0;i<n;i++) {
        memset(vis, falsesizeof(bool)*(m));
        if(dfs(i) == false)
            return false;
    }
    return true;
}
int main() {
    while(~scanf("%d%d" , &n, &m)) {
        memset(cnt, 0, sizeof(int)*(n));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                scanf("%d", &g[i][j]);
        for(int i=0;i<m;i++)
            scanf("%d", &capacity[i]);
        if(hungary(n) == true)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}
posted @ 2015-02-13 16:23 JulyRina 阅读(1146) | 评论 (0)编辑 收藏
题目大意:动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。 
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。 
有人用两种说法对这N个动物所构成的食物链关系进行描述: 
第一种说法是"1 X Y",表示X和Y是同类。 
第二种说法是"2 X Y",表示X吃Y。 
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。 
1) 当前的话与前面的某些真的话冲突,就是假话; 
2) 当前的话中X或Y比N大,就是假话; 
3) 当前的话表示X吃X,就是假话。 
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。 
题目分析;由于N和K很大,所以必须高效的维护动物之间的关系,并快速判断是否残生了矛盾,所以决定采用并查集。
对于每只动物i创建3个元素i,i+N,i+2N,并用这3*N个元素创建并查集。这个并查集维护如下信息:
i+xN表示“i属于种类x”。
并查集里的每一个组表示组内所有元素代表的都同时发生或不发生。
同时,在合并之前先判断合并是否会产生矛盾。
#include <cstdio>
#include <iostream>
using namespace std;

const int maxn = 50050;

int father[maxn*3], n, m, ans;

void init() {
    for(int i=0;i<3*n;i++) father[i] = i;
}
int find(int x) {
    return x == father[x] ? x : father[x] = find(father[x]);
}
void unite(int x, int y) {
    int a = find(x) , b = find(y);
    father[a] = father[b] = father[x] = father[y] = min(a, b);
}
bool check(int d, int x, int y) {
    if(x >= n || y >= n || x < 0 || y < 0)
        return false;
    if(d == 2 && x == y) 
        return false;
    if(d == 1) {
        if(find(x) == find(y+n) || find(x) == find(y+2*n))
            return false;
        unite(x, y);
        unite(x+n, y+n);
        unite(x+2*n, y+2*n);
        return true;
    } else {
        if(find(x) == find(y) || find(x) == find(y+2*n))
            return false;
        unite(x, y+n);
        unite(x+n, y+2*n);
        unite(x+2*n, y);
        return true;
    }
}
int main() {
    scanf("%d%d" , &n, &m);
    init();
    ans = 0;
    for(int i=0;i<m;i++) {
        int d, x, y;
        scanf("%d%d%d", &d, &x, &y);
        x --; y --;
        if(check(d, x, y) == false)
            ans ++;
    }
    printf("%d\n", ans);
    return 0;
}
posted @ 2015-02-11 17:33 JulyRina 阅读(153) | 评论 (0)编辑 收藏
题目大意:给定长度为N的字符串S,要构造一个长度为N的字符串T。起初,T是一个空串,随后反复进行下列任意操作。
从S的头部删除一个字符,加到T的尾部
从S的尾部删除一个字符,加到T的尾部
目标是构造字典序尽可能小的字符串。
题目分析;从字典序的性质上看,无论T的末尾有多大,只要前面部分较小就可以。所以我们可以试一下如下贪心算法:
不断取S和T的末尾中较小的一个字符放到T的末尾
这个算法已经接近正确了,只是针对S的开头和末尾字符相同的情形还没有定义。在这种情况下,因为我们希望能够尽早使用更小的字符,所以就要比较一下下一个字符的大小。下一个字符也有可能相同,因此就有如下算法:
按照字典序比较字符串S和S反转后的字符串S'。
如果S较小,就从S的开头取出一个文字,放到T的末尾。
如果S'较小,就从S的末尾取出一个文字,放到T的末尾。
(若果相同则去哪一个都可以)
#include <cstdio>

char s[2002], tmp[2];
int n;

int main() {
    while(~scanf("%d", &n)) {
        for(int i=0;i<n;i++) {
            scanf("%s", tmp);
            s[i] = tmp[0];
        }
        int l = 0, r = n - 1, cnt = 0;
        while(l <= r) {
            int i = 0, left = true;
            while(l + i <= r - i) {
                if(s[l+i] < s[r-i]) {
                    break;
                }
                if(s[l+i] > s[r-i]) {
                    left = false;
                    break;
                }
                i ++;
            }
            if(left == true) putchar(s[l++]);
            else putchar(s[r--]);
            cnt ++;
            if(cnt % 80 == 0) putchar('\n');
        }
        if(cnt % 80) putchar('\n');
    }
    return 0;
}
posted @ 2015-02-11 15:59 JulyRina 阅读(1959) | 评论 (0)编辑 收藏
题目大意:有一个大小为N*M的园子,雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼?
(八连通指下图中相当于W的*)
***
*W*
***
题目分析;从任意的W开始,不同的用一个vis数组标记是否访问过。一次DFS后与初始的这个W相连的W就都被标记过了。因此知道途中不再存在W为止,总共进行DFS的次数就是答案了。
#include <cstdio>
#include <cstring>

const int maxn = 101;

int n, m, ans;
char g[maxn][maxn];
bool vis[maxn][maxn];

void dfs(int x, int y) {
    if(vis[x][y] == true || g[x][y] != 'W') return;
    vis[x][y] = true;
    for(int i=-1;i<=1;i++)
    for(int j=-1;j<=1;j++) {
        if(!i && !j || x + i < 0 || x + i >= n || y + j < 0 || y + j >= m) continue;
        dfs(x+i, y+j);
    }
    return;
}

int main() {
    while(~scanf("%d%d" , &n, &m)) {
        for(int i=0;i<n;i++) {
            scanf("%s", g[i]);
            memset(vis+i, falsesizeof(bool)*(m));
        }
        ans = 0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                if(g[i][j] == 'W' && !vis[i][j]) {
                    ans ++;
                    dfs(i, j);
                }
        printf("%d\n", ans);
    }
    return 0;
}
posted @ 2015-02-11 15:29 JulyRina 阅读(401) | 评论 (0)编辑 收藏
仅列出标题
共3页: 1 2 3