LOJ-UOJ 模板

ACM

模板

tips

认真仔细读题！！！！确定题意

每一次交题前注意以下的事情：

  1. 看数据范围是否到了long long 而没有开
  2. 多造几组数据测试
  3. 数组有没有开大

最大流

题目描述

这是一道模板题。

给定 n 个点，m 条边，给定每条边的容量，求从点 s 到点 t 的最大流。

输入格式

第一行四个整数 n,m,s,t
接下来的 m 行，每行三个整数 u,v,c 表示 u 到 v ，流量为c的一条边

代码

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
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rep(i,x,y) for (int i=x; i<=y; ++i)
int get()
{
    static const int S=1<<16;
    static char pool[S],*tp=pool;
    #define getchar() (tp<pool+S? 0:fread(tp=pool,1,S,stdin),*tp++)
	char c;
	while (!isdigit(c=getchar()));
	int k=c-'0';
	for (; isdigit(c=getchar()); k=k*10+c-'0');
	return k;
}
using namespace std;
typedef long long ll;
const int N=110;
struct edge
{
	int v,c;
	edge *nxt,*rev;
} pool[10010],*tp=pool,*fst[N],*cur[N];
int n,m,src,ter,dis[N],gap[N];
ll ans;
int isap(int x,int mx=1<<30)
{
	if (x==ter)
		return mx;
	int s=0,r;
	for (edge *&i=cur[x]; i; i=i->nxt)
		if (i->c && dis[x]==dis[i->v]+1)
		{
			r=isap(i->v,min(mx-s,i->c));
			i->c-=r,i->rev->c+=r,s+=r;
			if (s==mx)
				return s;
		}
	if (!--gap[dis[x]])
		dis[src]=n;
	return ++gap[++dis[x]],cur[x]=fst[x],s;
}
int main()
{
	n=get(),m=get(),src=get(),ter=get();
	rep(i,1,m)
	{
		int u=get(),v=get(),c=get();
		*tp=(edge){v,c,fst[u],tp+1},fst[u]=tp++;
		*tp=(edge){u,0,fst[v],tp-1},fst[v]=tp++;
	}
	copy(fst+1,fst+n+1,cur),gap[0]=n;
	while (dis[src]<n)
		ans+=isap(src);
	printf("%lld",ans);
	return 0;
}

最小费用流

费用可以改成double,注意float 比double 快很多。。。

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
const int maxn = 20000;
namespace mincostflow {
	const int INF=0x3f3f3f3f;
	struct node {
		int to; int cap,cost; int rev;
		node(int t=0,int c=0,int _c=0,int n=0):
			to(t),cap(c),cost(_c),rev(n) {};
	}; vector<node> edge[maxn];
	void addedge(int from,int to,int cap,int cost) {
		edge[from].push_back(node(to,cap,cost,edge[to].size()));
		edge[to].push_back(node(from,0,-cost,edge[from].size()-1));
	}
	int dis[maxn];
	bool mark[maxn];
	void spfa(int s,int t,int n) {
		memset(dis+1,0x3f,n*sizeof(int));
		memset(mark+1,0,n*sizeof(bool));
		static int Q[maxn],ST,ED;
		dis[s]=0; ST=ED=0; Q[ED++]=s;
		while (ST!=ED) {
			int v=Q[ST]; mark[v]=0;
			if ((++ST)==maxn) ST=0;
			for (node &e:edge[v]) {
				if (e.cap>0&&dis[e.to]>dis[v]+e.cost) {
					dis[e.to]=dis[v]+e.cost;
					if (!mark[e.to]) {
						if (ST==ED||dis[Q[ST]]<=dis[e.to]) {
							Q[ED]=e.to,mark[e.to]=1;
							if ((++ED)==maxn) ED=0;
						} else {
							if ((--ST)<0) ST+=maxn;
							Q[ST]=e.to,mark[e.to]=1;
						}
					}
				}
			}
		}
	} int cur[maxn];
	int dfs(int x,int t,int flow) {
		if (x==t||!flow) return flow;
		int ret=0; mark[x]=1;
		for (int &i=cur[x];i<(int)edge[x].size();i++) {
			node &e=edge[x][i];
			if (!mark[e.to]&&e.cap) {
				if (dis[x]+e.cost==dis[e.to]) {
					int f=dfs(e.to,t,min(flow,e.cap));
					e.cap-=f; edge[e.to][e.rev].cap+=f;
					ret+=f; flow-=f;
					if (flow==0) break;
				}
			}
		} mark[x]=0;
		return ret;
	}
	pair<int,int> min_costflow(int s,int t,int n) {
		int ret=0,ans=0;
		int flow = INF;
		while (flow) {
			spfa(s,t,n); if (dis[t]==INF) break;
			memset(cur+1,0,n*sizeof(int));
			int len=dis[t],f;
			while ((f=dfs(s,t,flow))>0)
				ret+=f,ans+=len*f,flow-=f;
		} return make_pair(ret,ans);//最大流，最小费用
	}
	void init(int n) {
		int i; for (int i = 1; i <= n; i++) edge[i].clear();
	}
}
int n, m;
using namespace mincostflow;
int main(int argc, char const *argv[])
{
	scanf("%d %d", &n, &m);//n个点，m条边
	init(n);//点的个数
	for (int i = 1; i <= m; i++) {//建边
		int x, y, z, s;
		scanf("%d %d %d %d", &x, &y, &z, &s);
		addedge(x, y, z, s);
	}
	pair<int,int> ans = min_costflow(1, n, n);//s,t,点的个数
	printf("%d %d\n", ans.first, ans.second);//最大流，最小费用
	return 0;
}

无源汇有上下界可行流

题目描述

这是一道模板题。

n 个点，m 条边，每条边 e 有一个流量下界 lower(e) 和流量上界 upper(e) ，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制

输入格式

第一行两个正整数 n、m。

之后的 m 行，每行四个整数 s 、t 、lower、upper。

输出格式

如果无解，输出一行 NO。

否则第一行输出 YES，之后 m 行每行一个整数，表示每条边的流量。

代码

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
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int MX=215,mx=0x3f3f3f3f;
int n,m,S,T;
struct E{
	int t,c,f;E* r;
	E(int _t=0,int _c=0,int _f=0,E* _r=NULL):t(_t),c(_c),f(_f),r(_r){}
}pool[MX*MX],*G[MX],*cur[MX];
struct Edge{
	int f,t,c;E* e;
	Edge(int _f=0,int _t=0,int _c=0):f(_f),t(_t),c(_c){}
}e[MX*MX];int ec;
int sl[MX],D[MX],lw[MX*MX];
int q[MX],d[MX],vis[MX];
inline void ade(int f,int t,int c){
	e[++ec]=Edge(f,t,c),++D[f],++D[t];
}
bool bfs(){
	memset(vis+1,0,sizeof(int)*T);
	int h=0,t=0;
	q[++t]=S;d[S]=1,vis[S]=1;
	while(h<t){
		int r=q[++h];
		for(E* i=G[r];i!=G[r+1];i++)
		if(i->c>i->f&&!vis[i->t]){
			q[++t]=i->t,d[i->t]=d[r]+1,vis[i->t]=1;
		}
	}
	return vis[T];
}
int dfs(int k,int mx){
	if(k==T||!mx)return mx;
	int ans=0;
	for(E* &i=cur[k];i!=G[k+1];i++){
		if(i->c>i->f&&d[i->t]==d[k]+1){
			int f=dfs(i->t,min(mx,i->c-i->f));
			i->f+=f,i->r->f-=f;
			ans+=f,mx-=f;
			if(!mx)break;
		}
	}
	return ans;
}
int dinic(){
	int ans=0;
	while(bfs()){
		memcpy(cur+1,G+1,sizeof(E*)*T);
		ans+=dfs(S,mx);
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	S=n+1,T=n+2;
	for(int i=1;i<=m;i++){
		int s,t,l,u;
		scanf("%d%d%d%d",&s,&t,&l,&u);
		lw[i]=l;
		ade(s,t,u-l);sl[s]+=l,sl[t]-=l;
	}
	for(int i=1;i<=n;i++)if(sl[i]){
		if(sl[i]<0)ade(S,i,-sl[i]);
		else ade(i,T,sl[i]);
	}
	G[1]=pool;for(int i=1;i<=T;i++)G[i+1]=G[i]+D[i];
	for(int i=1;i<=ec;i++){
		--D[e[i].f],--D[e[i].t];
		e[i].e=G[e[i].f]+D[e[i].f];
		G[e[i].f][D[e[i].f]]=E(e[i].t,e[i].c,0,G[e[i].t]+D[e[i].t]);
		G[e[i].t][D[e[i].t]]=E(e[i].f,0,0,G[e[i].f]+D[e[i].f]);
	}
	dinic();
	//for(int i=1;i<=ec;i++)printf("%d %d %d %d\n",e[i].f,e[i].t,e[i].e->c,e[i].e->f);
	for(int i=m+1;i<=ec;i++)if(e[i].e->f<e[i].e->c){
		printf("NO\n");return 0;
	}
	printf("YES\n");
	for(int i=1;i<=m;i++)printf("%d\n",lw[i]+e[i].e->f);
	return 0;
}

有源汇有上下界最大流

题目描述

这是一道模板题。

n 个点，m 条边，每条边 e 有一个流量下界 lower(e)和流量上界 upper(e)，给定源点 s 与汇点 t，求源点到汇点的最大流。

输入

第一行两个正整数 n 、m、s、t。

之后的 m行，每行四个整数 s、t、lower、upper。

输出要求

如果无解，输出一行 please go home to sleep。

否则输出最大流。

代码

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
#include <cstdio>
#include <cmath>
#include <climits>
#include <algorithm>
#include <queue>
const int MAXN = 202;
struct Node
{
	struct Edge *firstEdge, *currEdge;
	int level, extraIn;
} N[MAXN + 2];
struct Edge
{
	Node *from, *to;
	int cap, flow;
	Edge *next, *revEdge;
	Edge(Node *from, Node *to, int cap) : from(from), to(to), cap(cap), flow(0), next(from->firstEdge) {}
};
struct Dinic
{
	bool makeLevelGraph(Node *s, Node *t, int n)
	{
		for (int i = 0; i < n; i++)
		{
			N[i].level = 0;
			N[i].currEdge = N[i].firstEdge;
		}
		std::queue<Node *> q;
		q.push(s);
		s->level = 1;
		while (!q.empty())
		{
			Node *v = q.front();
			q.pop();
			for (Edge *e = v->firstEdge; e; e = e->next)
			{
				if (e->flow < e->cap && !e->to->level)
				{
					e->to->level = v->level + 1;
					if (e->to == t) return true;
					else q.push(e->to);
				}
			}
		}
		return false;
	}
	int findPath(Node *s, Node *t, int limit = INT_MAX)
	{
		if (s == t) return limit;
		for (Edge *&e = s->currEdge; e; e = e->next)
		{
			if (e->to->level == s->level + 1 && e->flow < e->cap)
			{
				int flow = findPath(e->to, t, std::min(limit, e->cap - e->flow));
				if (flow)
				{
					e->flow += flow;
					e->revEdge->flow -= flow;
					return flow;
				}
			}
		}
		return 0;
	}
	int operator()(int s, int t, int n)
	{
		int res = 0;
		while (makeLevelGraph(&N[s], &N[t], n))
		{
			int flow;
			while ((flow = findPath(&N[s], &N[t])) > 0) res += flow;
		}
		return res;
	}
} dinic;
inline void addEdge(int from, int to, int cap)
{
	N[from].firstEdge = new Edge(&N[from], &N[to], cap);
	N[to].firstEdge = new Edge(&N[to], &N[from], 0);
	N[from].firstEdge->revEdge = N[to].firstEdge;
	N[to].firstEdge->revEdge = N[from].firstEdge;
}
inline void addEdge(int from, int to, int lower, int upper)
{
	int cap = upper - lower;
	addEdge(from, to, cap);
	N[to].extraIn += lower;
	N[from].extraIn -= lower;
}
// 原图的节点编号为 [1, n]
// 超级源点、汇点会占用 0 与 n + 1
//
// 所以总节点要开 MAXN + 2
inline int flow(int s, int t, int n)
{
	addEdge(t, s, INT_MAX);
	int S = 0, T = n + 1;
	int sum = 0;
	for (int i = 1; i <= n; i++)
	{
		if (N[i].extraIn > 0)
		{
			addEdge(S, i, N[i].extraIn);
			sum += N[i].extraIn;
		}
		else if (N[i].extraIn < 0)
		{
			addEdge(i, T, -N[i].extraIn);
		}
	}
	// 求可行流，满足下界
	int flow = dinic(S, T, n + 2);
	if (flow < sum) return -1;
	// 直接增广得到最大流
	return dinic(s, t, n + 2);
}
int main()
{
	int n, m, s, t;
	scanf("%d %d %d %d", &n, &m, &s, &t);
	while (m--)
	{
		int u, v, lower, upper;
		scanf("%d %d %d %d", &u, &v, &lower, &upper);
		addEdge(u, v, lower, upper);
	}
	
	int ans = flow(s, t, n);
	if (ans == -1) puts("please go home to sleep");
	else printf("%d\n", ans);
	return 0;
}

有源汇有上下界最小流

题目描述

n 个点，m 条边，每条边 e有一个流量下界 lower(e)和流量上界 upper(e)，给定源点 s与汇点 t，求源点到汇点的最小流。

代码

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
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iostream>
using namespace std;
const int N = 150010;
const int INF = 1e9;
struct Edge
{
    int to,nxt,c;
} e[500100];
int head[N],dis[N],cur[N],M[N];
int q[500100],L,R;
int tot = 1,n,m,S,T,Sum;
inline char nc()
{
    static char buf[100000],*p1 = buf,*p2 = buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    int x = 0,f = 1;
    char ch = nc();
    for (; ch<'0'||ch>'9'; ch=nc()) if(ch=='-') f=-1;
    for (; ch>='0'&&ch<='9'; ch=nc()) x=x*10+ch-'0';
    return x * f;
}
void add_edge(int u,int v,int c)
{
    e[++tot].to = v,e[tot].c = c,e[tot].nxt = head[u],head[u] = tot;
}
bool bfs()
{
    for (int i=1; i<=n+2; ++i)
        cur[i] = head[i],dis[i] = -1;
    L = 1,R = 0;
    q[++R] = S;
    dis[S] = 0;
    while (L <= R)
    {
        int u = q[L++];
        for (int i=head[u]; i; i=e[i].nxt)
        {
            int v = e[i].to;
            if (dis[v] == -1 && e[i].c > 0)
            {
                dis[v] = dis[u] + 1;
                q[++R] = v;
                if (v == T) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int flow)
{
    if (u == T) return flow;
    int used = 0;
    for (int &i=cur[u]; i; i=e[i].nxt)
    {
        int v = e[i].to;
        if (dis[v] == dis[u] + 1 && e[i].c > 0)
        {
            int tmp = dfs(v,min(e[i].c,flow-used));
            if (tmp > 0)
            {
                e[i].c -= tmp;
                e[i^1].c += tmp;
                used += tmp;
                if (used == flow) break;
            }
        }
    }
    if (used != flow) dis[u] = -1;
    return used;
}
int dinic(int s,int t)
{
    S = s,T = t;
    int ans = 0;
    while (bfs()) ans += dfs(S,INF);
    return ans;
}
int main ()
{
    n = read(),m = read();
    int s = read(),t = read();
    int ss = n + 1,tt = n + 2;
    for (int i=1; i<=m; ++i)
    {
        int u = read(),v = read(),b = read(),c = read();
        add_edge(u,v,c-b);
        add_edge(v,u,0);
        M[u] -= b;
        M[v] += b;
    }
    for (int i=1; i<=n; ++i)
    {
        if (M[i] > 0) add_edge(ss,i,M[i]),add_edge(i,ss,0),Sum += M[i];
        if (M[i] < 0) add_edge(i,tt,-M[i]),add_edge(tt,i,0);
    }
    add_edge(t,s,INF); //-
    add_edge(s,t,0);
    if (dinic(ss,tt) != Sum)
    {
        printf("please go home to sleep");
        return 0;
    }
    int ans = e[tot].c;
    e[tot].c = 0;
    e[tot ^ 1].c = 0;
    ans -= dinic(t,s);
    printf("%d",ans);
    return 0;
}

最快的二分图 hdu 6346

思路就是取反，整体最大变成最小，然后跑km就可以了

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
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int N = 210;
int val[N][N];
LL lx[N],ly[N];
int linky[N];
LL pre[N];
bool vis[N];
bool visx[N],visy[N];
LL slack[N];
int n;
void bfs(int k) {
    LL px, py = 0,yy = 0, d;
    memset(pre, 0, sizeof(LL) * (n+2));
    memset(slack, inf, sizeof(LL) * (n+2));
    linky[py]=k;
    do {
        px = linky[py],d = INF, vis[py] = 1;
        for(int i = 1; i <= n; i++)
            if(!vis[i]) {
                if(slack[i] > lx[px] + ly[i] - val[px][i])
                    slack[i] = lx[px] + ly[i] - val[px][i], pre[i] = py;
                if(slack[i] < d)
                    d = slack[i], yy = i;
                }
        for(int i = 0; i <= n; i++)
            if(vis[i])
                lx[linky[i]] -= d, ly[i] += d;
            else
                slack[i] -= d;
        py = yy;
        }
    while(linky[py]);
    while(py)
        linky[py] = linky[pre[py]], py=pre[py];
    }
void KM() {
    memset(lx, 0, sizeof(int)*(n+2));
    memset(ly, 0, sizeof(int)*(n+2));
    memset(linky, 0, sizeof(int)*(n+2));
    for(int i = 1; i <= n; i++)
        memset(vis, 0, sizeof(bool)*(n+2)), bfs(i);
    }
int main() {
    int T;
    scanf("%d", &T);
    for(int _i = 1; _i <= T; _i++) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                scanf("%d", &val[i][j]);
                val[i][j] = -val[i][j];
                }
            }
        KM();
        LL ans = 0;
        for(int i = 1; i <= n; ++i)
            ans += lx[i] + ly[i];
        printf("Case #%d: %I64d\n", _i, -ans);
        }
    return 0;
}

无向图的最小割 poj2914

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
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=606;
using namespace std;
int mat[N][N];
int res;
void Mincut(int n)  //注意写的时候不要丢node
{
    int dist[N],node[N];
    bool vis[N];
    for(int i=0; i<n; ++i) node[i]=i;
    while(n>1)
    {
        int maxx=1,prev=0;
        for(int i=1; i<n; ++i)
        {
            dist[node[i]]=mat[node[0]][node[i]];
            if(dist[node[i]]>dist[node[maxx]]) maxx=i;
        }
        memset(vis,0,sizeof(vis));  //每次都要更新vis
        vis[node[0]]=1;
        for(int i=1; i<n; ++i)
        {
            if(i==n-1)
            {
                res=min(res,dist[node[maxx]]);
                for(int k=0; k<n; ++k)
                    mat[node[k]][node[prev]]=(mat[node[prev]][node[k]]+=mat[node[maxx]][node[k]]);  //看清楚這
                node[maxx]=node[--n];
            }
            vis[node[maxx]]=1;
            prev=maxx;
            maxx=-1;
            for(int j=1; j<n; ++j) if(!vis[node[j]])
            {
                dist[node[j]]+=mat[node[prev]][node[j]];  //更新的时候注意是prev,因为在更新的时候顺便把下一次循环的最大值搞了出来
                if(maxx==-1||dist[node[j]]>dist[node[maxx]])  
                    maxx=j;
            }
        }
    }
    return ;
}
int main(){
   int n,m;
   while(scanf("%d%d",&n,&m)!=EOF){
    res=100861199;
    int u,v,w;
    memset(mat,0,sizeof(mat));
    while(m--){
        scanf("%d%d%d",&u,&v,&w);
        mat[u][v]+=w;
        mat[v][u]+=w;
    }
    Mincut(n);
    printf("%d\n",res);
   }
}

在线动态图连通性

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
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
const int MaxL = 16, N = 5005;
char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline int _R() {
	int d = 0; bool ty = 1; char t;
	while (t = GC, (t < '0' || t > '9') && t != '-');
	t == '-' ? (ty = 0) : (d = t - '0');
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return ty ? d : -d;
}
inline int RD() {
	static int seed = 20010916;
	return seed =( (seed ^ 21323123)* 998244353 + 1234321237) & 0x7fffffff;
}
int n, m;
struct Graph {	//
	set<int> mt[N];
	void add(int x, int y) {
		mt[x].insert(y);
		mt[y].insert(x);
	}
	
	void del(int x, int y) {
		mt[x].erase(y);
		mt[y].erase(x);
	}
	bool find(int x, int y) {
		return mt[x].count(y);
	}
	bool empty(int x) { return mt[x].empty(); }
} G[MaxL];
struct Node {
	Node *Son[2], *fa;
	bool hav;
	int pid, tid, sz, w;
} pool[10000000], *bin[10000000], *null;
int tl;
void ninit() {
	null = pool;
	null -> Son[0] = null -> Son[1] = null -> fa = null;
	for (int i = 1; i < N * MaxL; i ++) bin[i] = pool + i;
}
struct ETT {
	Graph *G;
	set<int> e[N];
	map<int, int> mt[N];
	Node *End[2000005], *id[N]; int tote;
	Node* newnode(int id, int tid) {
		Node *x = bin[++ tl];
		x -> pid = id;
		x -> tid = tid;
		x -> w = RD();
		x -> hav = id && !G -> empty(id);
		x -> sz = 1;
		x -> Son[0] = x -> Son[1] = x -> fa = null;
		return x;
	}
	void delnode(Node *x) {
		bin[tl --] = x;
	}
	void pushup(Node *x) {
		x -> hav = (x -> pid && !G -> empty(x -> pid)) || x -> Son[0] -> hav || x -> Son[1] -> hav;
		x -> sz = x -> Son[0] -> sz + x -> Son[1] -> sz + 1;
	}
	void split_up(Node *x, Node *&l, Node *&r) {
		if (x -> fa == null) return;
		Node *y = x -> fa; x -> fa = null;
		if (y -> Son[0] == x) {
			y -> Son[0] = r;
			r -> fa = y;
			pushup(y);
			r = y;
		}
		else {
			y -> Son[1] = l;
			l -> fa = y;
			pushup(y);
			l = y;
		}
		split_up(y, l, r);
	}
	void split(Node *x, Node *&l, Node *&r) {
		l = x -> Son[0], r = x -> Son[1];
		x -> Son[0] = x -> Son[1] = l -> fa = r -> fa = null;
		pushup(x);
		split_up(x, l, r);
	}
	Node* merge(Node *l, Node *r) {
		if (l == null || r == null) return l == null ? r : l;
		if (RD()&16) {
			l -> Son[1] = merge(l -> Son[1], r);
			l -> Son[1] -> fa = l;
			pushup(l);
			return l;
		}
		else {
			r -> Son[0] = merge(l, r -> Son[0]);
			r -> Son[0] -> fa = r;
			pushup(r);
			return r;
		}
	}
	void makeroot(Node *&x) {
		if (x == null) return;
		Node *l, *r;
		split(x, l, r);
		x = merge(merge(x, r), l);
	}
	Node* findrt(Node *x) {
		while (x -> fa != null) x = x -> fa;
		while (x -> Son[0] != null) x = x -> Son[0];
		return x;
	}
	Node *findrt(int x) {
		return findrt(id[x]);
	}
	void add(int u, int v, bool lev) {
		Node *x = id[u], *y = id[v];
		if (x != null && y != null && findrt(x) == findrt(y)) {
			pushup(x), pushup(y);
			while (x -> fa != null) x = x -> fa, pushup(x);
			while (y -> fa != null) y = y -> fa, pushup(y);
			return;
		}
		makeroot(x), makeroot(y);
		End[++ tote] = newnode(x == null ? u : 0, u), mt[u][v] = tote;
		End[++ tote] = newnode(y == null ? v : 0, v), mt[v][u] = tote;
		if (lev) e[u].insert(v), e[v].insert(u);
		merge(merge(merge(End[tote - 1], y), End[tote]), x);
		if (x == null) id[u] = End[tote - 1];
		if (y == null) id[v] = End[tote];
	}
	void getid(int x) {
		if (mt[x].empty()) { id[x] = null; return; }
		id[x] = End[mt[x].begin() -> second];
		Node *l, *r;
		split(id[x], l, r);
		id[x] -> pid = x; pushup(id[x]);
		merge(merge(id[x], r), l);
	}
	int del(int u, int v) {
		int eid = mt[u][v];
		mt[u].erase(v), mt[v].erase(u);
		Node *x = End[eid], *y = End[eid ^ 1], *l, *r;
		split(x, l, r);
		merge(r, l);
		split(y, l, r);
		int t0 = l -> sz,
			t1 = r -> sz;
		if (x -> pid) getid(u);
		if (y -> pid) getid(v);
		delnode(x), delnode(y);
		return t1 < t0 ? u : v;
	}
	
	void init(int x) {
		tote = 1;
		fill(id, id + n + 1, null);
		G = :: G + x;
	}
	void _print(Node *p) {
		if (p -> Son[0] != null) _print(p -> Son[0]);
		printf("%d ", p -> tid);
		if (p -> Son[1] != null) _print(p -> Son[1]);
	}
	void print(int x) {
		Node *p = id[x];
		if (p == null) return;
		makeroot(p);
		_print(p);
		puts("");
	}
} T[MaxL];
namespace D_Graph {
	void addlevel(int level, Node *x) {
		if (x == null || !x -> hav) return;
		if (x -> pid) {
			int u = x -> pid;
			for (auto v : T[level].e[u]) if (u < v) {
				G[level].del(u, v);
				G[level + 1].add(u, v);
				T[level + 1].add(u, v, 1);
			}
			T[level].e[u].clear();
		}
		addlevel(level, x -> Son[0]);
		addlevel(level, x -> Son[1]);
		T[level].pushup(x);
	}
	Node *xrt;
	int X, Y;
	bool findin_G(int level, int x) {
		while (!G[level].empty(x)) {
			int u = *G[level].mt[x].begin();
			if (T[level].findrt(u) != xrt) {
				X = x, Y = u;
				return 1;
			}
			G[level].del(x, u);
			G[level + 1].add(x, u);
			T[level + 1].add(x, u, 0);
		}
		return 0;
	}
	bool findin_T(int level, Node *x) {
		if (x == null || !x -> hav) return 0;
		if (x -> pid) if (findin_G(level, x -> pid)) return 1;
		if (findin_T(level, x -> Son[0])) return 1;
		if (findin_T(level, x -> Son[1])) return 1;
		x -> hav = 0;
		return 0;
	}
	
	void find_replacement(int level, int x) {
		Node *p = T[level].id[x];
		xrt = p;
		if (p == null) findin_G(level, x);
		else T[level].makeroot(p), addlevel(level, p), findin_T(level, p);
	}
	void add(int x, int y) {
		G[0].add(x, y);
		T[0].add(x, y, 1);
	}
	void del(int x, int y) {
		for (int i = MaxL - 1; i >= 0; i --) if (G[i].find(x, y)) {
			G[i].del(x, y);
			if (!T[i].mt[x].count(y)) return;
			T[i].e[x].erase(y);
			T[i].e[y].erase(x);
			X = Y = 0;
			for (int j = i; j >= 0; j --) {
				//if (!T[j].mt[x].count(y)) {
					//printf("assertion failed : level %d\n", j);
					//exit(0);
				//}
				int t = T[j].del(x, y);
				if (!X) {
					find_replacement(j, t);
					if (X) T[j].add(X, Y, 1);
				}
				else T[j].add(X, Y, 0);
			}
			return;
		}
	}
	bool isconnected(int x, int y) {
		return T[0].id[x] != null && T[0].id[y] != null && T[0].findrt(x) == T[0].findrt(y);
	}
}
int main() {
	//freopen("dgraph2.in", "r", stdin);
	int i, opt, x, y, ans = 0;
	n = _R(), m = _R();
	ninit();
	for (i = 0; i < MaxL; i ++) T[i].init(i);
	for (i = 1; i <= m; i ++) {
		opt = _R(), x = _R() ^ ans, y = _R() ^ ans;
		assert(x && y);
		if (opt == 0) /*printf("Add %d %d\n", x, y), */D_Graph :: add(x, y);
		else if (opt == 1) /*printf("Del %d %d\n", x, y), */D_Graph :: del(x, y);
		else {
			ans = D_Graph :: isconnected(x, y);
			puts(ans ? "Y" : "N");
			ans = ans ? x : y;
		}
		//T[0].print(1);
		//T[0].print(2);
	}
}

loj140 最小树形图

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
/*
最小树形图
朱刘算法模板
时间复杂度O(nm)
数据为int型
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1010
#define MAXM 1000000+10
#define INF 0x3f3f3f3f
#include <iostream>
using namespace std;
struct Edge
{
    int from, to, cost;
};
Edge edge[MAXM];
int pre[MAXN];//存储父节点
int vis[MAXN];//标记作用
int id[MAXN];//id[i]记录节点i所在环的编号
int in[MAXN];//in[i]记录i入边中最小的权值
int N, M, r;//N个点 M条有向边
int zhuliu(int root, int n, int m, Edge *edge)//root根 n点数 m边数
{
    int res = 0, u, v;
    while(1)
    {
        for(int i = 0; i < n; i++)
            in[i] = INF;//初始化
        for(int i = 0; i < m; i++)
        {
            Edge E = edge[i];
            if(E.from != E.to && E.cost < in[E.to])
            {
                pre[E.to] = E.from;//记录前驱
                in[E.to] = E.cost;//更新
            }
        }
        for(int i = 0; i < n; i++)
            if(i != root && in[i] == INF)
                return -1;//有其他孤立点 则不存在最小树形图
        //找有向环
        int tn = 0;//记录当前查找中 环的总数
        memset(id, -1, sizeof(id));
        memset(vis, -1, sizeof(vis));
        in[root] = 0;//根
        for(int i = 0; i < n; i++)
        {
            res += in[i];//累加
            v = i;
            //找图中的有向环 三种情况会终止while循环
            //1,直到出现带有同样标记的点说明成环
            //2,节点已经属于其他环
            //3,遍历到根
            while(vis[v] != i && id[v] == -1 && v != root)
            {
                vis[v] = i;//标记
                v = pre[v];//一直向上找
            }
            //因为找到某节点属于其他环  或者 遍历到根  说明当前没有找到有向环
            if(v != root && id[v] == -1)//必须上述查找已经找到有向环
            {
                for(int u = pre[v]; u != v; u = pre[u])
                    id[u] = tn;//记录节点所属的 环编号
                id[v] = tn++;//记录节点所属的 环编号  环编号累加
            }
        }
        if(tn == 0) break;//不存在有向环
        //可能存在独立点
        //cout<<"test1"<<" "<<tn<<endl;
        for(int i = 0; i < n; i++)
            if(id[i] == -1){
                id[i] = tn++;//环数累加
                //cout<<i<<endl;
            }
        //cout<<"test2"<<tn<<endl;
        //对有向环缩点  和SCC缩点很像吧
        for(int i = 0; i < m; i++)
        {
            v = edge[i].to;
            edge[i].from = id[edge[i].from];
            edge[i].to = id[edge[i].to];
            //<u, v>有向边
            //两点不在同一个环 u到v的距离为 边权cost - in[v]
            if(edge[i].from != edge[i].to)
                edge[i].cost -= in[v];//更新边权值 继续下一条边的判定
        }
        n = tn;//以环总数为下次操作的点数 继续执行上述操作 直到没有环
        root = id[root];
//        for(int i=0; i<N; i++){
//            cout<<id[i]<<" ";
//        }
//        cout<<endl;
    }
    return res;
}
void getMap(){
    int u, v, w;
    for(int i=0; i<M; i++){
        scanf("%d%d%d", &u, &v, &w);
        edge[i] = Edge{u-1, v-1, w};
    }
}
int main()
{
    while(scanf("%d%d%d", &N, &M, &r) != EOF)
    {
        getMap();//建图  注意去除自环  自己到自己的权值为无穷大
        int ans = zhuliu(r-1, N, M, edge);
        if(ans == -1)
            printf("-1\n");//不存在
        else
            printf("%d\n", ans);
    }
    return 0;
}

统计极大团的个数 poj2989

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
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 130;
bool mp[maxn][maxn];
int some[maxn][maxn], none[maxn][maxn], all[maxn][maxn];
int n, m, ans;
void dfs(int d, int an, int sn, int nn)
{
	if(!sn && !nn) ++ans;
	int u = some[d][0];
	for(int i = 0; i < sn; ++i)
	{
		int v = some[d][i];
		if(mp[u][v]) continue;
		for(int j = 0; j < an; ++j)
		all[d+1][j] = all[d][j];
		all[d+1][an] = v;
		int tsn = 0, tnn = 0;
		for(int j = 0; j < sn; ++j)
		if(mp[v][some[d][j]])
		some[d+1][tsn++] = some[d][j];
		for(int j = 0; j < nn; ++j)
		if(mp[v][none[d][j]])
		none[d+1][tnn++] = none[d][j];
		dfs(d+1, an+1, tsn, tnn);
		some[d][i] = 0, none[d][nn++] = v;
		if(ans > 1000) return;
	}
}
int work()
{
	ans = 0;
	for(int i = 0; i < n; ++i) some[1][i] = i+1;
	dfs(1, 0, n, 0);
	return ans;
}
int main()
{
	while(~scanf("%d %d", &n, &m))
	{
		memset(mp, 0, sizeof mp);
		for(int i = 1; i <= m; ++i)
		{
			int u, v;
			scanf("%d %d", &u, &v);
			mp[u][v] = mp[v][u] = 1;
		}
		int tmp = work();
		if(tmp > 1000) puts("Too many maximal sets of friends.");
		else printf("%d\n", tmp);
	}
	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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 130;
bool mp[maxn][maxn];
int some[maxn][maxn], none[maxn][maxn], all[maxn][maxn];
int n, m, ans;
void dfs(int d, int an, int sn, int nn)
{
	if(!sn && !nn) ans = max(ans, an);
	int u = some[d][0];
	for(int i = 0; i < sn; ++i)
	{
		int v = some[d][i];
		if(mp[u][v]) continue;
		for(int j = 0; j < an; ++j)
		all[d+1][j] = all[d][j];
		all[d+1][an] = v;
		int tsn = 0, tnn = 0;
		for(int j = 0; j < sn; ++j)
		if(mp[v][some[d][j]])
		some[d+1][tsn++] = some[d][j];
		for(int j = 0; j < nn; ++j)
		if(mp[v][none[d][j]])
		none[d+1][tnn++] = none[d][j];
		dfs(d+1, an+1, tsn, tnn);
		some[d][i] = 0, none[d][nn++] = v;
	}
}
int work()
{
	ans = 0;
	for(int i = 0; i < n; ++i) some[1][i] = i+1;
	dfs(1, 0, n, 0);
	return ans;
}
int main()
{
	while(~scanf("%d", &n) && n)
	{
		for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= n; ++j)
		{
			int x; scanf("%d", &x);
			mp[i][j] = mp[j][i] = x;
		}
		printf("%d\n", work());
	}
	return 0;
}

未解决的问题

本文标题:LOJ-UOJ 模板

文章作者:Babydragon

发布时间:2018-11-09, 20:36:21

最后更新:2018-11-22, 17:53:07

原始链接:http://baolintian.github.io/2018/11/09/LOJ-UOJ-模板/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. tips
  2. 2. 最大流
    1. 2.1. 题目描述
    2. 2.2. 输入格式
    3. 2.3. 代码
  3. 3. 最小费用流
  4. 4. 无源汇有上下界可行流
    1. 4.1. 题目描述
    2. 4.2. 输入格式
    3. 4.3. 输出格式
    4. 4.4. 代码
  5. 5. 有源汇有上下界最大流
    1. 5.1. 题目描述
    2. 5.2. 输入
    3. 5.3. 输出要求
    4. 5.4. 代码
  6. 6. 有源汇有上下界最小流
    1. 6.1. 题目描述
    2. 6.2. 代码
  7. 7. 最快的二分图 hdu 6346
  8. 8. 无向图的最小割 poj2914
  9. 9. 在线动态图连通性
  10. 10. loj140 最小树形图
  11. 11. 统计极大团的个数 poj2989
  12. 12. 最大团的点的个数
  13. 13. 未解决的问题
{{ live2d() }}