Change of Scenery（次短路）

Change of Scenery

题意

求是否存在一条不同于最短路但长度相同的路。

  1. 求次短路是否等于最短路
  2. dijstra的时候标记一下

看！代码

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
//求次短
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN (10000 + 10)
#define INF (5000*5000*2)
using namespace std;

struct edge
{
    int to, cost;
    edge(int tv = 0, int tc = 0):
        to(tv), cost(tc) {}
};
typedef pair<int,int> P;
int N, R;
vector<edge> graph[MAXN];
int dist[MAXN];     //最短距离
int dist2[MAXN];    //次短距离

void solve()
{
    fill(dist, dist+N, INF);
    fill(dist2, dist2+N, INF);
    //从小到大的优先队列
    //使用pair而不用edge结构体
    //是因为这样我们不需要重载运算符
    //pair是以first为主关键字进行排序
    priority_queue<P, vector<P>, greater<P> > Q;
    //初始化源点信息
    dist[0] = 0;
    Q.push(P(0, 0));
    //同时求解最短路和次短路
    while(!Q.empty())
    {
        P p = Q.top();
        Q.pop();
        //first为s->to的距离，second为edge结构体的to
        int v = p.second, d = p.first;
        //当取出的值不是当前最短距离或次短距离，就舍弃他
        if(dist2[v] < d) continue;
        for(unsigned i = 0; i < graph[v].size(); i++)
        {
            edge &e = graph[v][i];
            int d2 = d + e.cost;
            if(dist[e.to] > d2)
            {
                swap(dist[e.to], d2);
                Q.push(P(dist[e.to], e.to));
            }
            if(dist2[e.to] > d2 && dist[v] < d2)
            {
                dist2[e.to] = d2;
                Q.push(P(dist2[e.to], e.to));
            }
        }
    }
}
int main()
{
    int A, B, D,K;
    scanf("%d%d%d", &N, &R,&K);
    while(K--)
        scanf("%d",&A);
    for(int i = 0; i < R; i++)
    {
        scanf("%d%d%d", &A, &B, &D);
        graph[A-1].push_back(edge(B-1, D));
        graph[B-1].push_back(edge(A-1, D));
    }
    solve();
    if(dist2[N-1]==dist[N-1])
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}

展开全文 >>

Bounty Hunter II（最小路径覆盖）

# Bounty Hunter II

题意

求最小路径覆盖数（不交叉），套最大流模板即可。

结点总数-匹配数=覆盖数

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
#include <bits/stdc++.h>
using namespace std;
const int N=5010;
const int M=3000010;
const int inf=0x3f3f3f3f;
struct Edge
{
    int v,cap,nxt;
}e[M];;//邻接表要开边数的两倍
int src,des,dis[N],head[N],ecnt;  //memset dis,head-1 ecnt=0,src=0,des=2*n+1;
int n,m;
void Addedge(int u,int v,int w)
{
    e[ecnt].v=v;
    e[ecnt].cap=w;
    e[ecnt].nxt=head[u];
    head[u]=ecnt++;
    e[ecnt].v=u;
    e[ecnt].cap=0;
    e[ecnt].nxt=head[v];
    head[v]=ecnt++;
}
bool Bfs()
{
    queue<int>q;
    q.push(src);
    memset(dis,-1,sizeof(dis));
    dis[src]=0;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];~i;i=e[i].nxt)
        {
            int v=e[i].v;
            if(e[i].cap>0&&dis[v]==-1)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[des]>=0;
}
int Dfs(int u,int a)
{
    if(u==des) return a;
    for(int i=head[u];~i;i=e[i].nxt)
    {
        int v=e[i].v,t=0;
        if(e[i].cap>0&&dis[v]==dis[u]+1&&(t=Dfs(v,min(a,e[i].cap))))
        {
            e[i].cap-=t;
            e[i^1].cap+=t;
            return t;
        }
    }
    dis[u]=-1;
    return 0;
}
int Dinic()
{
    int ans=0;
    while(Bfs())
    {
        int t=0;
        while(t=Dfs(src,inf)) ans+=t;
    }
    return ans;
}
int main()
{
    int num,u,v;
    ecnt=0;
    memset(head,-1,sizeof(head));
    scanf("%d",&num);
    src=0;des=2*num+1;
    for(int i=1;i<=num;i++)
        Addedge(0,i,1);
    for(int i=num+1;i<=2*num;i++)
        Addedge(i,2*num+1,1);
    for(int i=1;i<=num;i++)
    {
        scanf("%d",&u);
        while(u--)
        {
            scanf("%d",&v);
            Addedge(i,num+v+1,1);
        }
    }
    n=num+2;
    printf("%d\n",num-Dinic());
    return 0;
}

展开全文 >>

HDU 6315 Naive Operations(线段树)

HDU 6315 Naive Operations

n个数，q个询问

起始a、b数组都是n个元素，a数组全是0，b是1~n的全排列

add l r ：a中【l，r】都加1

query l r ：询问∑floor(ai/bi) (i : l~r)

思路：

区间更新的线段树，维护区间最小值min（bi-ai%bi） 当min=0时sum++。

具体看代码注释

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <bits/stdc++.h>
#define MAXN 100010
#define inf 0x3f3f3f3f

using namespace std;

struct node{
    long long l,r;//区间[l,r]
    long long add;//区间的延时标记
    long long sum;//区间和
    long long mn; //区间最小值
    long long bi; //对应bi
}tree[MAXN<<2];//一定要开到4倍多的空间

void pushup(int index)
{
    tree[index].sum = tree[index<<1].sum+tree[index<<1|1].sum;
    tree[index].mn = min(tree[index<<1].mn,tree[index<<1|1].mn);
}
void pushdown(int index)
{
    //说明该区间之前更新过
    //要想更新该区间下面的子区间，就要把上次更新该区间的值向下更新
    if(tree[index].add)
    {
        tree[index<<1].mn -= tree[index].add;
        tree[index<<1|1].mn -= tree[index].add;
        tree[index<<1].add += tree[index].add;
        tree[index<<1|1].add += tree[index].add;
        tree[index].add = 0;
    }
}
void print(int l,int r,int index) //测试数据 输出具体
{
    printf("l:%d r:%d bi:%lld min:%lld sum:%lld lazy:%d\n",l,r,tree[index].bi,tree[index].mn,tree[index].sum,tree[index].add);
    if(tree[index].l==tree[index].r)
    {
         return;
    }
    int mid=(l+r)>>1;
    print(l,mid,index<<1);
    print(mid+1,r,index<<1|1);
}
void build(int l,int r,int index)
{
    tree[index].l = l;
    tree[index].r = r;
    tree[index].add = 0;//刚开始一定要清0
    tree[index].sum=0;
    if(l == r)
    {
        scanf("%lld",&tree[index].bi);
        tree[index].mn = tree[index].bi;
        tree[index].sum=0;
        return ;
    }
    int mid = (l+r)>>1;
    build(l,mid,index<<1);
    build(mid+1,r,index<<1|1);
    pushup(index);
}
void updata(int l,int r,int index)
{
    if(l<=tree[index].l&&r>=tree[index].r&&tree[index].mn>1) 
    {
        tree[index].mn--;
        tree[index].add++;
        return ;
    }
    if(tree[index].l==tree[index].r)
    {
        tree[index].mn--;
        tree[index].add++;
        if(tree[index].mn<=0)
        {
            tree[index].sum++;
            tree[index].mn=tree[index].bi;
        }
        return ;
    }
    pushdown(index);
    int mid = (tree[index].l+tree[index].r)>>1;

    if (r <= mid) updata(l,r,index<<1);
    else if (l>mid) updata(l,r,index<<1|1);
    else {
        updata(l,mid,index<<1);
        updata(mid+1,r,index<<1|1);
    }

    pushup(index);
}
long long query(int l,int r,int index)
{
    if(l == tree[index].l && r == tree[index].r)
        return tree[index].sum;

    pushdown(index);
    int mid = (tree[index].l+tree[index].r)>>1;
    long long ans = 0;
    if(r<=mid) ans = query(l,r,index<<1);
    else if(l>mid) ans = query(l,r,index<<1|1);
    else{
        return ans = query(l,mid,index<<1)+query(mid+1,r,index<<1|1);
    }
    pushup(index);
    return ans;
}
int main()
{
    int n,m,q,x,y,z;
    char s[100];
    while(~scanf("%d%d",&n,&m)){
    build(1,n,1);
    while(m--)
    {
        scanf("%s%d%d",s,&x,&y);
        if(s[0] =='q' )
            printf("%lld\n",query(x,y,1));
        else
            updata(x,y,1);
    //    print(1,n,1);
     //   printf("m:%d\n",m);
    }
    }
    return 0;
}
/*
5 12
1 5 2 4 3
add 1 4
query 1 4
add 2 5
query 2 5
add 3 5
query 1 5
add 2 4
query 1 4
add 2 5
query 2 5
add 2 2
query 1 5
*/

展开全文 >>

测时间 

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
#include<windows.h>
int main()
{
    DWORD start_time=GetTickCount();
    {
        //此处为被测试代码
    }
    DWORD end_time=GetTickCount();
    cout<<"The run time is:"<<(end_time-start_time)<<"ms!"<<endl;//输出运行时间
    return 0;
}

展开全文 >>

飞行员配对(最大流模板)

看！代码

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
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int MAXN = 201;

int g[MAXN][MAXN];        //残留网络，初始为原图
int flow[MAXN][MAXN];
int nodeNum;            //节点总数量
int pre[MAXN];

//bfs找增广路
int bfs(const int &s, const int &t)
{
    int que[201],p,q,v,i;
    for (i=0;i<=nodeNum+1;i++)
        pre[i]=-1;
    que[0]=s;
    pre[s]=s;
    p=0,q=1;
    while(p<q)
    {
        v=que[p++];
        for(i=0;i<=nodeNum+1;i++)
            if (pre[i]==-1&&(flow[v][i]<g[v][i]||flow[i][v]>0))
            {
                pre[i]=v;
                que[q++]=i;
                if (i==t) return 1;
            }
    }
    return 0;
}

//修改残留矩阵和增广路
void track_back(const int &s, const int &t)
{
    int i=t,v,MIN=INF;
    while (i!=s)
    {
        v = pre[i];
        if (flow[v][i]<g[v][i])
        {
            if(MIN>g[v][i]-flow[v][i])
                MIN=g[v][i]-flow[v][i];
        }
        else if (flow[i][v]>0)
        {
            if(MIN>flow[i][v])
                MIN=flow[i][v];
        }
        i=v;
    }
    i=t;
    while (i!=s)
    {
        v = pre[i];
        if (flow[v][i]<g[v][i])
            flow[v][i]+=MIN;
        else if (flow[i][v]>0)
            flow[i][v]-= MIN;
        i = v;
    }
}

//返回 从节点s到节点t的最大流
int max_flow(const int &s, const int &t)
{
    while (bfs(s,t))
        track_back(s,t);
    int res=0,i;
    for (i=0;i<=nodeNum+1;i++)
        if (i!=s)res+=flow[s][i];
    return res;
}

int main()
{
    int m,b,e,c;
    scanf("%d%d",&m,&nodeNum);
    memset(g,0,sizeof(g));
    memset(flow,0,sizeof(flow));
    while (scanf("%d%d",&b,&e))
    {
        if(b==-1&&e==-1) break;
        g[e][b]=1;
    }
    for(int i=1;i<=m;i++)
        g[i][nodeNum+1]=1;

    for(int i=m+1;i<=nodeNum;i++)
        g[0][i]=1;

    printf("%d\n",max_flow(0,nodeNum+1));
    return 0;
}


展开全文 >>

网络流 【待续】

例如：有一个自来水管道输送系统，起点是S，目标是T，图中经过的管道都有一个最大的容量：

水管流量最大该是多少呢

网络流的定义

在有向图G=（V,E）中：

1、有唯一的一个源点S（入度为0：出发点）

2、有唯一的一个汇点（出度为0：结束点）

3、图中的每条弧（u,v）都有一个非负的容量c（u,v）

满足上述条件的图G称为网络流图。

记为：G=（V,E,C）

more >>

展开全文 >>

Clever King (最大权闭合子图模板)

Clever King

题意

T组数据，有n个产品，m个矿坑。接下来n个数字happiness[i]表示第i个产品的幸福指数，接下来m个数字，ori[i]表示第i个矿坑的开发费用。接下来n行，每行先输入两个数字n1，n2，分别表示第i号产品需要开发的矿坑，和需要的原材料产品。（矿坑开发后材料无限，产品生产后幸福指数一定会增加，不管是作为产品本身还是原材料），要求 幸福指数 - 费用 的最大值。

思路

最大权闭合子图模板。【关于网络流】（ND）

定义

一个子图（点集）， 如果它的所有的出边都在这个子图当中，那么它就是闭合子图。
点权和最大的闭合子图就是最大闭合子图。

简单说就是有一些点，每个点有一些点权（正负都有），要选一个点，就必须要选它所连向的点。

有可能连成一条链，像这样：x->y->z->…

求合法的点集的最大的点权和。

构图

设s为源点，t为汇点。

使s连向所有的正权点（非负权点），边权为点权。

使所有非负权点（负权点）连向t，边权为点权的绝对值。

若需要选y才能选x，连一条由x到y的边，边权是∞。

最大点权和 = 正权点和 - 最小割

看！代码

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=505;
struct node{
    int to,next,flow;
}e[maxn*maxn*2];
int cur[maxn],co[maxn],d[maxn],Final[maxn],tot,s,t;
// s源点 t终点

void link(int x,int y,int z)
{
    e[++tot].to=y,e[tot].next=Final[x],e[tot].flow=z,Final[x]=tot;
    e[++tot].to=x,e[tot].next=Final[y],e[tot].flow=0,Final[y]=tot;
}
int dg(int x,int flow) //模板 
{
    if(x==t) return flow;
    int use=0;
    for(int i=cur[x];i;i=e[i].next)
    {
        cur[x]=i;
        if(e[i].flow>0&&d[e[i].to]+1==d[x])
        {
            int c=dg(e[i].to,min(flow-use,e[i].flow));
            use+=c;
            e[i].flow-=c;
            e[i^1].flow+=c;
            if(flow==use) return use;
        }
    }
    cur[x]=Final[x];
    if(!(--co[d[x]])) d[0]=t;
    ++co[++d[x]];
    return use;
}
int main()
{
    int T,n1,n2,temp,n,m;
    int ans;
    long long sum;
    scanf("%d",&T);
    while(T--)
    {
        sum=0;tot=1;s=t=0;
        memset(cur,0,sizeof(cur));
        memset(co,0,sizeof(co));
        memset(d,0,sizeof(d));
        memset(Final,0,sizeof(Final));
        scanf("%d%d",&n,&m);
        ans=n+m;s=ans+1;t=ans+2;
        for(int i=1;i<=n;i++) //s和正权相连
        {
            scanf("%d",&temp);
            sum+=temp;
            link(s,i,temp);
        }
        for(int i=1;i<=m;i++)  //t和负权相连
        {
            scanf("%d",&temp);
            link(i+n,t,temp);
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&n1,&n2);
            for(int j=1;j<=n1;j++)  //i个点需要j的话，就把i->j，边权是inf
            {
                scanf("%d",&temp);
                link(i,temp+n,1<<30);
            }
            for(int j=1;j<=n2;j++)
            {
                scanf("%d",&temp);
                link(i,temp,1<<30);
            }
        }
        co[0]=t;
        for(;d[0]<t;) sum-=dg(s,1<<30); //最小割
        printf("%lld\n",sum);
    }
    return 0;
}

展开全文 >>

Goldbach （Miller Rabin模板+埃氏筛模板)

Goldbach

题意

哥德巴赫猜想：输入一个T（100），输入一个偶数n（2<n<2^63），输出任意一组素数a，b，使得a+b=n。

思路

a和b必定为一大一小，从小的入手，用埃氏筛筛出1e6内的所有素数prim[]（猜想到小的那个素数一定不超过1e6），然后遍历prim[]，算出n-prim[i]，用基于概率的素数测试算法MillerRabin判断它是不是素数即可。

【Miller Rabin素数判定】

这里注意，由于2^63次过大，在相乘得过程中会超longlong，因此要改用unsigned long long。

做题的时候，遇到范围是2^63，取模2^64的这种题目。遇到这种限制条件时就要想到用unsigned long long类型。这样，如果ull类型的整数溢出了，就相当于取模2^64了。因为ull的范围是[0,2^64-1]。而ll的范围是[-2^63,2^63-1]，因为有符号的第63位表示“正负”而不表示数值。

附一个公式：(1+a1)(1+a2)(1+a3)……(1+an-1)(1+an) = 1+sum{ai}+sum{ai·aj}+sum{ai·aj·ak}+……+sum{a1·a2·…·an}

看！代码

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
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define MOD 1000000007
using namespace std;
const int MAXN = 65;
const int MAX=1e6;
typedef ULL ULL;
ULL n, x[MAXN];

ULL pri[MAX+5],num=0;
bool vis[MAX+5];

void init()
{
    int i,j;
    for(i=2;i<MAX;i++)
    {
        if(vis[i]==false)pri[num++]=i;
        for(j=0;j<num&&i*pri[j]<MAX;j++)
            vis[i*pri[j]]=true;
    }
}

ULL multi(ULL a, ULL b, ULL p) {
    ULL ans = 0;
    while(b) {
        if(b&1LL) ans = (ans+a)%p;
        a = (a+a)%p;
        b >>= 1;
    }
    return ans;
}

ULL qpow(ULL a, ULL b, ULL p) {
    ULL ans = 1;
    while(b) {
        if(b&1LL) ans = multi(ans, a, p);
        a = multi(a, a, p);
        b >>= 1;
    }
    return ans;
}

bool Miller_Rabin(ULL n) {
    if(n == 2) return true;
    int s = 20, i, t = 0;
    ULL u = n-1;
    while(!(u & 1)) {
        t++;
        u >>= 1;
    }
    while(s--) {
        ULL a = rand()%(n-2)+2;
        x[0] = qpow(a, u, n);
        for(i = 1; i <= t; i++) {
            x[i] = multi(x[i-1], x[i-1], n);
            if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1) return false;
        }
        if(x[t] != 1) return false;
    }
    return true;
}

int main()
{
    int t;
    ULL n,temp;
    init();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld",&n);
        for(int i=0;i<num;i++)
        {
            if(Miller_Rabin(n-pri[i]))
            {
                printf("%lld %lld\n",pri[i],n-pri[i]);break;
            }
        }
    }
    return 0;
}

展开全文 >>

ACM-ICPC & U

world final的直播，窝在图书馆的角落看了一下午，这种感觉真的很棒，真的让我有一种ACM即是力量的冲动。看着这么多的队伍们提交，Pending的进度条一点一点增加，然后高亮，切到队伍的镜头，一阵紧张，最后AC后的欢呼和击掌，然后匆匆进入下一题。

代码的力量是什么呢？

ACM的力量是什么呢？

让我明明笨拙到坚持不下去，却又不舍得放弃它。

大概是等待pending的期待的心情，WA了之后自言自语的不服，TLE绞尽脑汁优化的苦恼，或者是看着队友疯狂输出的感叹，大家叽里呱啦实在是很吵闹的讨论 …… 以及最后出现的世界上最好看的单词Accept的欣喜若狂。

真是充满着魔力的一切。

四月十九号，倒计时：三天。

许下演唱会的心愿。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

小可爱的小可爱，<br/>拖肥的娘亲，<br/>划水的ACMer，<br/>努力中的小菜鸡，<br/>想要自信和一往无前的勇气。