题目链接: poj 2516
题目大意: 给出N间商店和它们对K种商品的需求,再给出M个供应商和K种商品的库存
然后再给出第x种商品从j供应商运输到i商店的单位运输费用
求N间商店对商品的需求能否得到满足,并且输出最小费用
解题思路: 如果直接建图会超时,因为顶点数太多
所以根据每种商品,进行K次最小费用流:
1.建立超级源点,源点指向N间商店,容...
阅读全文
题目链接: poj 3614
题目大意: 给出N个区间,然后M个数,每个数最多可以匹配Ki次
问最多有多少个区间能被匹配
解题思路: 若按区间起点从小到大开始排,每个数按从小到大开始排
下面这种情况会过不了
1 9 6
2 6 9
既会出现k2可以同时匹配X1和X2,但k2只能匹配X1,若选择k1匹配x1则结果是错误的...
阅读全文
题目链接: poj 3281
题目大意: 有N头奶牛,A种食物和B种饮料,每头奶牛都有自己喜欢的食物和饮料
问有最多有多少头奶牛既可以得到自己喜欢的食物又可以得到喜欢的饮料
解题思路: 开始没有把奶牛分成两个点,这样会导致几种食物流入同一头奶牛
正确的构图:
1.建立超级源点,源点分别指向A种不同的食物,容量为1
2.建立超级汇点,B种不同的饮料...
阅读全文
题目链接: poj 2337
题目大意: 给出N个单词,单词A的开头与另外单词B结尾相同
则单词A和单词B可以连起来,问是否可以把所有单词都串成一条线
输出最小字典序的(按单词的字典序串)
解题思路: 对于每个单词,把单词的起点和终点字母当作顶点
这个单词即是起点到终点的一条单向边
根据有向图的欧拉图判断,若顶点的出度-入度为0,或者一个为1一个...
阅读全文
题目链接: poj 1041
题目大意: 给出无向图,每条边有唯一的序号
是否存在欧拉回路,若存在输出边序号最小字典序的路径
解题思路: 无向欧拉回路的判断方法,若存在奇数度点,则不存在欧拉回路
依据静态邻接链表的特性,从序号大到小建立边
因为这样总能保证序号最小的边首先访问到
PS:欧拉路径的问题要记得判断图是否联通
代码:
#include <...
阅读全文
题目链接: poj 3422
题目大意: 给出NxN的数字矩阵,左上角走到右下角(只能向右或向下走),sum记录走过点值的和
走过的点值置为0,问走K次,求sum的最大值
解题思路: 开始想到的是K次最长路,结果WA了
因为每次走最长路会导致下次走的时候不是最优解
建立费用流模型,把每个顶点T,分成两个顶点T和T''
因为要限制每个顶点的值只加一次,T->T...
阅读全文
题目链接:
poj 1088
题目大意: 给出NxM的矩阵,每个点的值都不同
若某点四个方向中某个方向的值比它小则可以移动,求能够走的最长步数
解题思路: 经典的状态压缩Dp,Dp[ x ][ y ]记录从(x , y)点出发能走的最长步数
Dp[ x ][ y ]=Max(Dp[ x ][ y ],DFS(xx , yy) + 1)
若某个点之前已经走过,则不用再走,直接返回之前所能走到的最大值
代码:
#include <stdi...
阅读全文