模板

发表于 | 分类于 ， | 阅读量 次

这是dddfaker的模板

1. 中国剩余定理

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
#中国剩余定理#

#define LL long long

LL gcd(LL a,LL b)
{
    return b==0?a:gcd(b,a%b);
}

LL ex_gcd(LL a,LL b,LL &x,LL &y)
{
    if(!b) {x=1;y=0;return a;}
    else {LL ans=ex_gcd(b,a%b,y,x);y-=x*(a/b);return ans;}
}

LL modeqset(LL a[],LL b[],LL n) // X==b(mod a)
{
    LL c,x,y,t,d;
    for(LL i=1;i<n;i++)
    {
        c=b[i]-b[i-1];
        d=ex_gcd(a[i-1],a[i],x,y);
        if(c%d)return -1;
        t=a[i]/d;
        x=(x*(c/d)%t+t)%t;
        b[i]=x*a[i-1]+b[i-1];
        a[i]=a[i-1]*(a[i]/d);
    }
    return b[n-1];
}

2. 强连通分量

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
#强连通分量#

#define maxn 233333

int dfn[maxn],low[maxn],head[maxn],ins[maxn],color[maxn];
int n,m;
int k;
int Bcnt;
int idx;
stack<int> s;

int cnt[maxn];
int in[maxn];
int visit[maxn];
int ehead[maxn];
int kk;
int dp[maxn];
int K=0;
int cas=0;

struct edge{
int v,Next;
}e[maxn],ee[maxn];


void add(int u,int v)
{
    e[k].v=v;
    e[k].Next=head[u];
    head[u]=k++;
}

void init()
{
    kk=k=1;
    Bcnt=0;
    idx=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(ins,0,sizeof(ins));
    memset(head,-1,sizeof(head));
    memset(ehead,-1,sizeof(ehead));
    memset(cnt,0,sizeof(cnt));
    memset(in,0,sizeof(in));
    memset(color,0,sizeof(color));
    memset(dp,0,sizeof(dp));
}


void tarjan(int u)
{
    int v;
    dfn[u]=low[u]=++idx;
    s.push(u);
    ins[u]=1;
    for(int i=head[u];i!=-1;i=e[i].Next)
    {
        v=e[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(ins[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        Bcnt++;
        do{
            v=s.top();
            color[v]=Bcnt;
            s.pop();
            ins[v]=0;
        }while(u!=v);
    }
}

void add2(int u,int v)
{
    ee[kk].v=v;
    ee[kk].Next=ehead[u];
    ehead[u]=kk++;
}


void work()
{
    for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
    if(Bcnt==1)
    {
        printf("%d\n",n);
        return;
    }
    for(int i=1;i<=n;i++) cnt[color[i]]++;
    for(int u=1;u<=n;u++)
        for(int i=head[u];i!=-1;i=e[i].Next)
            {
                int v=e[i].v;
                if(color[u]!=color[v])
                {
                    add2(color[v],color[u]);
                    in[color[u]]++;
                }
            }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        add(a,b);
        work();
    }

    return 0;
}

3. 双连通分量

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
#双连通分量#
#include <iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
using namespace std;
#define maxn 233333
#define INF 0x3f3f3f3f


int dfn[maxn],low[maxn],head[maxn],ehead[maxn],cnt[maxn],dp[maxn],mark[maxn],color[maxn];
struct Coke{
    int from,to,Next;
}e[maxn],ee[maxn];
int k,kk,Bcnt,idx,n,m,SUM,MIN;
stack<int>s;

void add(int u,int v)
{
    e[k].from=u;
    e[k].to=v;
    e[k].Next=head[u];
    head[u]=k++;
}

void add1(int u,int v)
{
    ee[kk].from=u;
    ee[kk].to=v;
    ee[kk].Next=ehead[u];
    ehead[u]=kk++;
}

void init()
{
    k=kk=Bcnt=idx=SUM=0;
    MIN=INF;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(head,-1,sizeof(head));
    memset(ehead,-1,sizeof(ehead));
    memset(cnt,0,sizeof(cnt));
    memset(dp,0,sizeof(dp));
    memset(mark,0,sizeof(mark));
    memset(color,0,sizeof(color));
}

void Tarjan(int u,int fa)
{
    int v;
    dfn[u]=low[u]=++idx;
    mark[u]=1;
    s.push(u);
    int flag=0;
    for(int i=head[u];i!=-1;i=e[i].Next)
    {
        v=e[i].to;
        if(v==fa&&!flag){flag=1;continue;}
        if(!mark[v]) Tarjan(v,u);
        low[u]=min(low[u],low[v]);
    }
    if(low[u]==dfn[u])
    {
        Bcnt++;
        do{
            v=s.top();
            s.pop();
            color[v]=Bcnt;
            dp[Bcnt]+=cnt[v];
        }while(u!=v);
    }
}

int dfs(int u,int fa)
{
    int sum=dp[u];
    for(int i=ehead[u];i!=-1;i=ee[i].Next)
    {
        int v=ee[i].to;
        if(v==fa) continue;
        sum+=dfs(v,u);
    }
    MIN=min(MIN,abs(SUM-2*sum));
    return sum;
}


int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=1;i<=n;i++)
            {scanf("%d",&cnt[i]);SUM+=cnt[i];}
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            a++,b++;
            add(a,b);
            add(b,a);
        }
        Tarjan(1,1);
        if(Bcnt==1) {printf("impossible\n");continue;}
        for(int i=1;i<=n;i++)
        {
            for(int j=head[i];j!=-1;j=e[j].Next)
            {
                int u=e[j].from,v=e[j].to;
                if(color[u]!=color[v]) add1(color[u],color[v]);
            }
        }
        dfs(1,0);
        printf("%d\n",MIN);
    }
    return 0;
}

4. 匈牙利（最大匹配）

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
#匈牙利（最大匹配）#
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int n,m,k;
int map1[110][110];
int visit[110];
int girl[110];

bool Find(int x)
{
    for(int i=1;i<m;i++)
    {
        if(map1[x][i]&&!visit[i])
        {
            visit[i]=1;
            if(!girl[i]||Find(girl[i]))
            {
                girl[i]=x;
                return 1;
            }
        }
    }
    return 0;
}

int main()
{
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d%d",&m,&k);
        memset(map1,0,sizeof(map1));
        memset(girl,0,sizeof(girl));
        while(k--)
        {
            int id,x,y;
            scanf("%d%d%d",&id,&x,&y);
            map1[x][y]=1;
        }
        int ans=0;
        for(int i=1;i<n;i++)
        {
            memset(visit,0,sizeof(visit));
            if(Find(i)) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}
/*二分图性质：
最小点覆盖=最大匹配。
最小边覆盖=最大独立集=图中点的个数-最大匹配。
*/

5. 最大团

5.1 dfs版

5.2 BK（Bron–Kerbosch）版：（最大团，极大团）

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
145
146
147
148
149
150
151
152
153
#最大团#

//dfs版：
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int N;
int GG[40][40];
int ans;
int now[40];
int dp[40];

void dfs(int x,int sum)
{
    if(sum>ans) ans=sum;
    if(sum+N-x<=ans) return;
    int tot=0;
    int tnow[40];
    for(int i=x+1;i<=N;i++)
    {
        tnow[i]=now[i];
        if(now[i])tot++;
    }
    if(sum+tot<=ans) return;
    for(int i=x+1;i<=N;i++)
    {
        if(!tnow[i]) continue;
        if(sum+dp[i]<=ans) continue;
        for(int j=1;j<=N;j++)
            now[j]=tnow[j]&GG[i][j];
        dfs(i,sum+1);
    }
    return;
}

int Huge()
{
    dp[N]=ans=1;
    for(int i=N-1;i>=1;i--)
    {

        for(int j=1;j<=N;j++)
            now[j]=GG[i][j];
        dfs(i,1);
        dp[i]=ans;
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&N)&&N)
    {
        memset(GG,0,sizeof(GG));
        for(int i=1;i<=N;i++)
        {
           //通过GG建立邻边关系
        }
        int F=Huge();
         printf("%d\n",F);
         }
    return 0;
}


//BK（Bron–Kerbosch）版：（最大团，极大团）
#include <iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

int a[130][130];
int ans;
int P[130][130];
int R[130][130];
int X[130][130];


bool BK(int d,int nr,int np,int nx)
{
    if(np==0&&nx==0)
    {
        ans++;
        if(ans>1000)
            return 1;
        return 0;
    }
    int u,max1=0;
    u=P[d][1];
    for(int i=1; i<=np; i++)
    {
        int cnt=0;
        for(int j=1; j<=np; j++)
            if(a[P[d][i]][P[d][j]])
                cnt++;
        if(cnt>max1)
        {
            max1=cnt;
            u=P[d][i];
        }
    }
    for(int i=1; i<=np; i++)
    {
        int v=P[d][i];
        if(a[v][u])continue;
        for(int j=1; j<=nr; j++)
            R[d+1][j]=R[d][j];
        R[d+1][nr+1]=v;
        int cnt1=0;
        for(int j=1; j<=np; j++)
            if(P[d][j]&&a[P[d][j]][v])
                P[d+1][++cnt1]=P[d][j];
        int cnt2=0;
        for(int j=1; j<=nx; j++)
            if(a[X[d][j]][v])
                X[d+1][++cnt2]=X[d][j];
                if(BK(d+1,nr+1,cnt1,cnt2))return 1;
            P[d][i]=0;
            X[d][++nx]=v;

            }
            return 0;
}


int main()
{
    int n,m;
    while(~scanf("%d%d",&n,&m))
    {
        memset(a,0,sizeof(a));
        while(m--)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            a[x][y]=a[y][x]=1;
        }

        ans=0;
        for(int i=1; i<=n; i++)
            P[1][i]=i;
        BK(1,0,n,0);
        if(ans>1000)
            printf("Too many maximal sets of friends.\n");
        else printf("%d\n",ans);
    }
    return 0;
}

6. 字典树

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
#字典树#

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int tree[5000000][26];
int tot=0;

void Insert (int root,char *s)
{
    for(;*s;s++)
    {
        int id=*s-'a';
        if(tree[root][id]==0) tree[root][id]=++tot;
        root=tree[root][id];
    }
    return;
}

int Search(int root,char *s)
{
    for(;*s;s++)
    {
        int id=*s-'a';
        if(tree[root][id]==0) return 0;
        root=tree[root][id];
    }
    return 1;
}

int main()
{
    char s[5005];
    int root=0;
    int ans;
    while(gets(s)&&s[0]!='\0')
    {
       Insert(root,s);
    }
    while(~scanf("%s",s))
    {
        ans=Search(root,s);
        printf("%d\n",ans);
    }

    return 0;
}

7. 矩阵快速幂

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
#矩阵快速幂#


const int N=9;
struct Matrix{///矩阵结构体 
    ll matrix[N][N];
};
 
const int mod = 1e9 + 7;
 
void init(Matrix &res)///初始化为单位矩阵 
{
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i=0;i<N;i++)
        res.matrix[i][i]=1;
}
Matrix multiplicative(Matrix a,Matrix b)///矩阵乘法
{
    Matrix res;
    memset(res.matrix,0,sizeof(res.matrix));
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            for(int k = 0 ; k < N ; k++){
                res.matrix[i][j] += a.matrix[i][k]*b.matrix[k][j];
                res.matrix[i][j] %= mod;
            }
        }
    }
    return res;
}
Matrix Pow(Matrix mx,ll m)///矩阵快速幂 
{
    Matrix res,base=mx;
    init(res);
    while(m)
    {
        if(m&1)
            res=multiplicative(res,base);
        base=multiplicative(base,base);
        m>>=1;
    }
    return res;
}

8. 最短路

8.1 Floyed

8.2 Dijkstra

8.3 SPFA

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
#最短路#

#define Max 0x3f3f3f3f
#define maxn 10010
int n,m;
int Map[maxn][maxn];
int dist[maxn];
int vist[maxn];

//Floyd：
void floyd()
{
    int i,j,k;
    for (k=1; k<=n; k++)
        for(i=1; i<=n; i++)
            for (j=1; j<=n; j++)
                Map[i][j]=min( Map[i][j],Map[i][k]+Map[k][j] );

}

//Dijkstra：
void Dijkstra(int s)
{
    int i,j;
    int u;
    int Min;
    for (i=1; i<=n; i++)
    {
        vist[i]=0;
        dist[i] = Map[s][i];
    }
    vist[s] = 1;
    for (i=1; i<=n; i++)
    {
        Min=Max;
        u = -1;
        for (j=1; j<=n; j++)
        {
            if (vist[j]==0&&dist[j]<Min)
            {
                u = j;
                Min = dist[j];
            }
        }
        if (u==-1)
            break;
        vist[u] = 1;
        for (j=1; j<=n; j++)
        {
            if(vist[j]==0)
            {
                if(dist[u]+Map[u][j]<dist[j])
                    dist[j] = dist[u]+Map[u][j];
            }
        }
    }
}

//SPFA
void spfa(int s)
{
    int i,now;
    for( i=1;i<=n;i++ )
    {
        dist[i]=Max;
        vist[i] = 0;
    }
    dist[s] = 0;
    queue<int>q;
    q.push(s);
    vist[s] = 1;
    while (!q.empty())
    {
        now = q.front();
        q.pop();
        vist[now] = 0;
        for( i=1;i<=n;i++)
        {
            if (dist[i]>dist[now]+Map[now][i])
            {
                dist[i] = dist[now]+Map[now][i];
                if (vist[i] == 0)
                {
                    q.push(i);
                    vist[i] = 1;
                }
            }
        }
    }

}

9. 线段树

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
#线段树#

#include<bits/stdc++.h>
using namespace std;
int n,p,a,b,m,x,y,ans;
struct node
{
    int l,r,w,f;
}tree[400001];
inline void build(int k,int ll,int rr)//建树 
{
    tree[k].l=ll,tree[k].r=rr;
    if(tree[k].l==tree[k].r)
    {
        scanf("%d",&tree[k].w);
        return;
    }
    int m=(ll+rr)/2;
    build(k*2,ll,m);
    build(k*2+1,m+1,rr);
    tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void down(int k)//标记下传 
{
    tree[k*2].f+=tree[k].f;
    tree[k*2+1].f+=tree[k].f;
    tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
    tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
    tree[k].f=0;
}
inline void ask_point(int k)//单点查询
{
    if(tree[k].l==tree[k].r)
    {
        ans=tree[k].w;
        return ;
    }
    if(tree[k].f) down(k);
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) ask_point(k*2);
    else ask_point(k*2+1);
}
inline void change_point(int k)//单点修改 
{
    if(tree[k].l==tree[k].r)
    {
        tree[k].w+=y;
        return;
    }
    if(tree[k].f) down(k);
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) change_point(k*2);
    else change_point(k*2+1);
    tree[k].w=tree[k*2].w+tree[k*2+1].w; 
}
inline void ask_interval(int k)//区间查询 
{
    if(tree[k].l>=a&&tree[k].r<=b) 
    {
        ans+=tree[k].w;
        return;
    }
    if(tree[k].f) down(k);
    int m=(tree[k].l+tree[k].r)/2;
    if(a<=m) ask_interval(k*2);
    if(b>m) ask_interval(k*2+1);
}
inline void change_interval(int k)//区间修改 
{
    if(tree[k].l>=a&&tree[k].r<=b)
    {
        tree[k].w+=(tree[k].r-tree[k].l+1)*y;
        tree[k].f+=y;
        return;
    }
    if(tree[k].f) down(k);
    int m=(tree[k].l+tree[k].r)/2;
    if(a<=m) change_interval(k*2);
    if(b>m) change_interval(k*2+1);
    tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
int main()
{
    scanf("%d",&n);//n个节点 
    build(1,1,n);//建树 
    scanf("%d",&m);//m种操作 
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&p);
        ans=0;
        if(p==1)
        {
            scanf("%d",&x);
            ask_point(1);//单点查询,输出第x个数 
            printf("%d",ans);
        } 
        else if(p==2)
        {
            scanf("%d%d",&x,&y);
            change_point(1);//单点修改 
        }
        else if(p==3)
        {
            scanf("%d%d",&a,&b);//区间查询 
            ask_interval(1);
            printf("%d\n",ans);
        }
        else
        {
             scanf("%d%d%d",&a,&b,&y);//区间修改 
             change_interval(1);
        }
    }
}

10. 树状数组

10.1 一维树状数组

10.2 二维树状数组

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
#树状数组#

//一维
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define lowbit(x) (x)&(-x)

int tree[50005];
int N;
void change(int x,int a)//添加数据
{
    while(x<=N)
    {
        tree[x]+=a;
        x+=lowbit(x);
    }
    return;
}

int ask(int x)//访问
{
    int sum=0;
    while(x>0)//这里二进制运算不能处理0
    {
        sum+=tree[x];
        x-=lowbit(x);
    }
    return sum;
}

//二维
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define lowbit(x) (x)&(-x)

int tree[1010][1010];

void change(int x,int y,int a)//添加数据
{
    for(int i=x; i<=1005; i+=lowbit(i))
        for(int j=y; j<=1005; j+=lowbit(j))
            tree[i][j]+=a;
    return;
}

int Sum(int x,int y)//访问
{
    int sum=0;
    for(int i=x; i>0; i-=lowbit(i))
        for(int j=y; j>0; j-=lowbit(j))
            sum+=tree[i][j];
    return sum;
}

11. 网络流

11.1 EK

11.2 dicnic

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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#网络流#

//EK
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
#define INF 0x3fffffff

int N,M;
int visit[210],pre[210];
int mp[210][210];
int ans;

void EK()
{
    while(1)//寻找增广路径
    {
        queue<int>q;
        memset(visit,0,sizeof(visit));//visit[]表示该点已经访问过
        memset(pre,0,sizeof(pre));//pre[]用来记录路径
        q.push(1);
        visit[1]=1;
        while(!q.empty())
        {
            int cnt=q.front();
            q.pop();
            if(cnt==M) break;//找到一条路径
            for(int i=1;i<=M;i++)
            {
                if(!visit[i]&&mp[cnt][i]>0){
                visit[i]=1;
                q.push(i);
                pre[i]=cnt;
            }
            }
        }
        if(!visit[M]) break;//没有找到一条通向M的路径

        int minx=INF;
        for(int i=M;i!=1;i=pre[i])
            minx=min(minx,mp[pre[i]][i]);//将路径上的最小残余容量作为该条路径上的最大流量

        for(int i=M;i!=1;i=pre[i])
        {
            mp[pre[i]][i]-=minx;//正边加
            mp[i][pre[i]]+=minx;//反边减（反悔用）
        }
        ans+=minx;//将路径上的最大流加到总的最大流中

    }

}


int main()
{
    while(~scanf("%d%d",&N,&M))
    {
        memset(mp,0,sizeof(mp));
        for(int i=1; i<=N; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            mp[a][b]+=c;//建图
        }
        ans=0;
        EK();
        printf("%d\n",ans);
    }
    return 0;
}


//dicnic
#include <iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
#define K 400105
#define INF 0x3fffffff

int S=0;//起源点
int E=300005;//总汇点

int tot;//记录边的编号
int to[K],cap[K],lev[K],Next[K],first[K];
/*
to[]记录边的尾点
cap[] 记录边的容量
lev[]记录边的等级，方便寻找一条增广路径
Next[]记录起点连接的下一条边的编号
first[]记录尾点的上一条边的编号
*/

void add(int u,int v,int w)
{
    to[tot]=v;
    cap[tot]=w;
    Next[tot]=first[u];
    first[u]=tot++;


    to[tot]=u;
    cap[tot]=0;
    Next[tot]=first[v];
    first[v]=tot++;
    return;
}

int dfs(int x,int flow)
{
    if(x==E||flow==0) return flow;
    int res=0;//res记录当前边已被使用的容量
    for(int i=first[x];i!=-1;i=Next[i])
    {
        if(flow-res>0&&lev[to[i]]==lev[x]+1&&cap[i])
        {
            int k=dfs(to[i],min(flow-res,cap[i]));
            if(!k) lev[to[i]]=0;
            cap[i]-=k;//正边
            cap[i^1]+=k;//反边
            res+=k;
        }
    }
    return res;
}

int bfs()
{
    queue<int>q;
    memset(lev,0,sizeof(lev));
    lev[S]=1;
    q.push(S);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(x==E) return 1;
        for(int i=first[x];i!=-1;i=Next[i])
        {
            if(cap[i]>0&&!lev[to[i]])
            {
                lev[to[i]]=lev[x]+1; //给点加上lev[]值，相当于寻找最短路
                q.push(to[i]);
            }
        }
    }
    return 0;
}

void init()
{
          memset(first,-1,sizeof(first));//初始所有first[]指向-1，表示无指向边
	tot=0;
}

int dicnic()
{
    int ans=0;
    while(bfs())//寻找增广路径
    {
        ans+=dfs(S,INF);//扩路
    }

    return ans;
}