uva 10253 - Series-Parallel Networks

标签：style   blog   class   c   code   ext   

今天起得比较晚，又浪费了点时间，真可耻。。

下午又为校赛出了俩题，至此，校赛的四道题目已经完毕。又检查了一番，没有错误，就等待着明天的汇总了~。

AC自动机的题目今天就刷了三道，还是没有完成之前的目标。现在vj也进不去了，想通宵，都不给机会~~

只能等明天再刷完了，拖延不是一个好习惯。

----------------------------------------------------------------------------------------------------------

1,hdu-4511-小明系列故事――女友的考验

抢了CZ的FB，心里很高兴，哈哈

AC自动机越来越模板了，就先创建非法路径的自动机。然后再树上求1点到n点的最短路。我当时没有注意要“只能走到比当前所在点编号大的位置； ”的条件，错了N次，伤心。。

#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define LL __int64
#define maxn 55
const int maxnode=110*5;
const int childnum=55;
const int mod=1000000007;
const int INF=99999999;
struct list
{
    double  x;
    double y;
}node[maxn];
struct listt
{
    int p;
    int t;
    double dis;
    friend bool operator b.dis;
    }
}pp,qq;
double dist(int x,int y)
{
    double xx,yy;
    xx=node[x].x-node[y].x;
    yy=node[x].y-node[y].y;
    double sum=xx*xx+yy*yy;
    return 1.0*sqrt(1.0*sum);
}
priority_queueque;
struct ac_tree
{
    int chd[maxnode][childnum];
    int val[maxnode];
    int fail[maxnode];
    int key[1vec,int k)
    {
        int p=0;
        int len=vec.size();
        for(int i=0;ivec;
        for(int i=1;i

2，hdu-4758-Walk Through Squares
1.对自动机上每个状态dp,dp[a][b][c][d]表示经过了a个字符，匹配了b个R，在c这个状态，d是4进制数，表示是否经过串1和串2
也就是一个树上DP，想好状态转移方程就好了。

#include
#include
#include
#include
#include
using namespace std;
#define LL int
const int maxnode=101*2;
const int childnum=2;
const int mod=1000000007;
const int INF=99999999;
struct ac_tree
{
    int chd[maxnode][childnum];
    int val[maxnode];
    int fail[maxnode];
    int key[1

3，hdu-4057- Rescue the Rabbit
dp[i][j][k]，表示长度为i的串，位于Trie上的状态j，模式串的状态为k的最大价值。
状态压缩一下，就变成了普通的树上DP了，还需要滚动数组压缩一下空间。

#include
#include
#include
#include
#include
using namespace std;
const int maxnode=101*10;
const int childnum=4;
const int mod=20090717;
const int INF=99999999;
struct ac_tree
{
    int chd[maxnode][childnum];
    int val[maxnode];
    int fail[maxnode];
    int key[1
















uva 10253 - Series-Parallel Networks,搜素材,soscw.com
uva 10253 - Series-Parallel Networks
标签：style   blog   class   c   code   ext   
原文地址：http://blog.csdn.net/keshuai19940722/article/details/26178279