图论模板（备战省赛）~~
1.最短路径（spfa）
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
int m, n;
int head[10000];
struct edge
{
int to;
int ne = -1;
int len;
}ed[10000];//储存边
int time[10000];//遍历次数
bool vis[10000];//是否访问
int d[10000];//每个节点的最短距离
int cnt = 0;//计数
void init()
{
for (int s = 0; s <= 9999; s++)
{
head[s] = -1;
}
for (int s = 0; s <= m; s++)
{
d[s] = 0x3f3f3f3f;
}
memset(vis, 0, sizeof(vis));
memset(time, 0, sizeof(time));
}
void add(int from, int to, int len)
{
ed[cnt].to = to;
ed[cnt].len = len;
ed[cnt].ne = head[from];
head[from] = cnt++;
}
int spfa()//默认1是起点；
{
d[1] = 0;
deque<int>q;
q.push_front(1);
vis[1] = 1;
bool flag = false;
while (!q.empty())
{
int t = q.front();
q.pop_front();
vis[t] = 0;
for (int s = head[t]; ~s; s = ed[s].ne)
{
if (d[ed[s].to] > d[t] + ed[s].len)
{
d[ed[s].to] = d[t] + ed[s].len;
if (!vis[ed[s].to])
{
vis[ed[s].to] = 1;
time[ed[s].to]++;
if (time[ed[s].to] > n)
{
flag = true;
}
if(!q.empty())//注意队列为空时的处理
{
if(d[ed[s].to]<d[q.front()])
{
q.push_front(ed[s].to);
}
else
{
q.push_back(ed[s].to);
}
}
else
{
q.push_front(ed[s].to);
}
}
}
}
}
return flag;
}
int main()
{
while (cin >> n >> m)
{
cnt = 0;
init();
for (int s = 0; s < m; s++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
int ans = spfa();
for (int i = 1; i <= n; i++)
printf("distance[%d] = %d\n", i, d[i]);
}
}
2.最小生成树~~
#include<cstdio>
#include<queue>
#include<iostream>
#include<algorithm>
using namespace std;
int fa[10005];并查集查询父亲节点
struct edg
{
int to;
int from;
int len;
}ed[10005];储存边
bool cmp(edg a, edg b)
{
return a.len < b.len;
}
void init()
{
for (int s = 0; s < 10000; s++)
{
fa[s] = s;
}
}
int tofind(int x)
{
if (fa[x] != x)
{
fa[x] = tofind(fa[x]);
}
return fa[x];
}
int tojoin(int a, int b)
{
a = tofind(a);
b = tofind(b);
//cout << a << " " << b << endl;
if (a != b)
{
fa[a] = b;
return 1;
}
return 0;
}
int main()
{
int n;
while (cin >> n)
{
init();
for (int s = 0; s < n; s++)
{
cin >> ed[s].from >> ed[s].to >> ed[s].len;
}
sort(ed, ed + n, cmp);
int sum = 0;
for (int s = 0; s < n; s++)
{
int a = tojoin(ed[s].from, ed[s].to);
sum = sum + ed[s].len*a;
cout << ed[s].from << " " << ed[s].to <<" "<< ed[s].len << " "<<a<<endl;
}
cout << sum << endl;
}
}
3.第k最短路（A*算法）~~
#include<stdio.h>
#include<string.h>
#include<vector>
#include<queue>
#define inf 1<<31-1
#define N 1011
using namespace std;
int dis[N], head1[N], head2[N];//前向星
struct node1
{
int v, w, next;
};
node1 edg1[N * 100], edg2[N * 100];
bool in_q[N];//相当于vis~；
struct node2//A*算法所需
{
int v, f, g;
bool operator <(const node2 &x)const
{
if (x.f == f) return x.g<g;
return x.f<f;
}
};
int h;//向前星
void initi(int n)
{
int i;
for (i = 0; i <= n; i++)
{
dis[i] = inf;
head1[i] = -1;
head2[i] = -1;
in_q[i] = false;
}
h = 0;
}
void add(int u, int v, int w)
{
edg1[h].v = v;
edg1[h].w = w;
edg1[h].next = head1[u];
head1[u] = h;
//正向图
edg2[h].v = u;
edg2[h].w = w;
edg2[h].next = head2[v];
head2[v] = h;
//反向图；
++h;
}
void spfa(int st, int ed)
{
queue<int>q;
q.push(st);
in_q[st] = true;
dis[st] = 0;
int si, ui, mdis, i;
while (!q.empty())
{
si = q.front();
q.pop();
in_q[si] = false;
for (i = head2[si]; i != -1; i = edg2[i].next)
{
ui = edg2[i].v;
mdis = dis[si] + edg2[i].w;
if (mdis<dis[ui]) {
dis[ui] = mdis;
if (!in_q[ui]) {
q.push(ui);
in_q[ui] = true;
}
}
}
}
// printf("%d \n",dis[ed]);
}
//启发式搜索。f(x) = g(x)到当前点的距离 + h(x)当前点到终点的距离。
int astar(int st, int ed, int k)
{
if (st == ed)
k++;
if (dis[st] == inf)//反向不连通，正向也必然不连通
return -1;
priority_queue<node2>q;//二级排序f,g从小到大！！！
node2 temp, ui;
temp.v = st;
temp.g = 0;
temp.f = temp.g + dis[temp.v];
q.push(temp);
int cnt = 0, i;
while (!q.empty())
{
temp = q.top();
q.pop();
if (temp.v == ed)
cnt++;
if (cnt == k)
return temp.g;
for (i = head1[temp.v]; i != -1; i = edg1[i].next)
{
ui.v = edg1[i].v;
ui.g = temp.g + edg1[i].w;
ui.f = ui.g + dis[ui.v];
q.push(ui);
}
}
return -1;
}
int main()
{
int n, m, i, ans;
int st, ed, k;
int a, b, d;
while (scanf("%d%d", &n, &m) != EOF)
{
initi(n);
for (i = 0; i<m; i++)
{
scanf("%d%d%d", &a, &b, &d);
add(a, b, d);
}
scanf("%d%d%d", &st, &ed, &k);//st是起点~~ed是终点~~k是所求的第k最短路
spfa(ed, st);
ans = astar(st, ed, k);//A*算法；
printf("%d\n", ans);
}
return 0;
}
4.二分图的最大匹配数（最小顶点覆盖~用点来覆盖边）
#include<cstdio>
#include<iostream>
using namespace std;
bool map[1005][1005];//关系；
int b_find[1005];//被选择的对象
bool use[1005];//在某一次查询中有没有被访问过
int ans = 0;
int g, b;//g是几个选择者~b是被选择者；
void init()
{
memset(map, 0, sizeof(map));
memset(b_find, 0, sizeof(b_find));
memset(use, 0, sizeof(use));
ans = 0;
}
int find(int x)
{
for (int s = 1; s <= b; s++)
{
if (map[x][s] && !use[s])
{
use[s] = 1;
if (!b_find[s] || find(b_find[s]))
{
b_find[s] = x;
return 1;
}
}
}
return 0;
}
int main()
{
int k;
while (~scanf("%d", &k) && k)
{
init();
scanf("%d %d", &g, &b);
while (k--)
{
int a, b;
scanf("%d %d", &a, &b);
map[a][b] = 1;
}
for (int s = 1; s <= g; s++)
{
memset(use, 0, sizeof(use));
if (find(s))
{
ans++;
}
}
cout << ans << endl;
}
return 0;
} 5、二分图中最小边覆盖=顶点数-最小顶点覆盖（最大匹配）（至少需要用多少边才能覆盖所有点）
6、二分图中最大独立集+最小顶点覆盖（最大匹配）=顶点数
7， 判断能否topo排序
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int maxn=100+10;
int n,m;
vector<int> G[maxn];//G[i]表示i节点所指向的所有其他点
int in[maxn];//节点入度
bool topo()//判断该图是否可拓扑排序
{
queue<int> Q;
int sum=0;//记录可拆解的点数目
for(int i=0;i<n;i++)if(in[i]==0)
Q.push(i);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
sum++;
for(int i=0;i<G[u].size();i++)
{
int v=G[u][i];
if(--in[v]==0) Q.push(v);
}
}
return sum==n;//可完全拓扑
}
int main()
{
while(scanf("%d%d",&n,&m)==2&&n)
{
memset(in,0,sizeof(in));
for(int i=0;i<n;i++) G[i].clear();
for(int i=0;i<m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
in[v]++;
}
printf("%s\n",topo()?"YES":"NO");
}
return 0;
} 8.反向topo
#include<cstdio>
#include<cstring>
#include<stack>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
int te;
int m,n;
int out[30005];
vector<int>g[30005];
stack<int>qu;//用来储存最终答案的
void topo()//本来的代码，应该是按入度来排序~可这道题决定输出顺序的是最后的哪位数（比如说之前提到的 3 1 2，因为1 应该在 2前面所以这样排列）
{
priority_queue<int>q;
for(int s=1;s<=n;s++)
{
if(out[s]==0)
{
q.push(s);//选择无出度的压入优先队列
// cout<<s<<endl;
}
}
while(!q.empty())
{
int tem=q.top();
qu.push(tem);
q.pop();
for(int s=0;s<g[tem].size();s++)
{
out[g[tem][s]]--;//解除与之的关系
if(out[g[tem][s]]==0)//无出度
{
q.push(g[tem][s]);//压入优先队列
}
}
}
int t=0;
while(!qu.empty())
{
if(t==0)//别忘了输出的格式
{
printf("%d",qu.top());
}
else
{
printf(" %d",qu.top());
}
t++;
qu.pop();
}
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin>>te;
while(te--)
{
memset(out,0,sizeof(out));//初始化
scanf("%d%d",&n,&m); //之前用了解除stdio的同步~以为这样时间就够用了，可是还是tle了；
int a,b;
for(int s=1;s<=n;s++)//初始化
{
g[s].clear();
}
while(m--)
{
scanf("%d%d",&a,&b);
g[b].push_back(a);
out[a]++;
}
topo();
}
return 0;
} 9.lca算法~~
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
int n;
int father[105]; //每个节点的父节点
int rnk[105]; //树中节点的个数
int ancestor[105]; //已访问节点集合的祖先
void initSet() {
for (int i = 0; i<n; i++) {
father[i] = i; //初始化时，所在子树的祖先就是自己
rnk[i] = 1; //所在树的深度为0
}
}
int findSet(int x) {
if (x != father[x])
father[x] = findSet(father[x]); //压缩式的查找，在查找过程中更新每个节点的祖先
return father[x];
}
void unionSet(int x, int y) { //合并子树,把节点数小的树合并到节点数大的树
x = findSet(x);
y = findSet(y);
if (x == y)
return;
if (rnk[x] >= rnk[y]) {
father[y] = x;
rnk[x] += rnk[y];
}
else {
father[x] = y;
rnk[y] += rnk[x];
}
}
int flag[105]; //记录点是否为访问过
vector<int> tree[105]; //树的表示
vector<int> query[105]; //查询的表示
void tarjan(int u)
{ //访问到集合u时
for (int i = 0; i<tree[u].size(); i++) {
int v = tree[u][i];
// cout << v << endl;//假设这个节点是v
tarjan(v);
unionSet(u, v); //将子节点和根节点合并,并查集的作用只是代表一个集合，仅仅当做一个集合使用
ancestor[findSet(u)] = u; //合并后的集合的祖先为u,只要标记这个集合的代表元素的祖先为x就行，这个集合
//内的其他元素能够通过findSet来找到代表，再利用代表找到祖先
}
flag[u] = 1;
for (int i = 0; i<query[u].size(); i++)
{
if (flag[query[u][i]]) //如果另外一个节点已经被访问过，则输出另外一个节点所在集合的祖先
cout << u << "和" << query[u][i] << "的最近公共祖先为:" << ancestor[findSet(query[u][i])] << endl; //找到节点query[u][i]所在集合的代表的祖先，
//也就是这个集合的祖先，只是用代表的ancestor值标记一下而已
}
}
int main()
{
initSet();
tree[1].push_back(2);
tree[1].push_back(3);
tree[2].push_back(4);
tree[3].push_back(5);
query[4].push_back(5);
query[5].push_back(4);
tarjan(1); //算的时候还是要用入度来找到最祖先
return 0;
} 10.次短路
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
using namespace std;
int m, n;
int head[100000];
#define inf 0x3f3f3f3f
struct edge
{
int to;
int ne;
int len;
}ed[500000];
bool vis[100000];
int d[100000]; //起点到各个点的距离
int d2[100000]; //终点到各个点的距离
int cnt = 0;
void init()
{
for (int s = 0; s <= 9999; s++)
{
head[s] = -1;
}
for (int s = 0; s < 490000; s++)
{
ed[s].ne = -1;
}
for (int s = 0; s <= n; s++)
{
d[s] = inf;
d2[s] = inf;
}
memset(vis, 0, sizeof(vis));
}
void add(int from, int to, int len)
{
ed[cnt].to = to;
ed[cnt].len = len;
ed[cnt].ne = head[from];
head[from] = cnt++;
}
void spfa(int e,int d[])
{
d[e] = 0;
queue<int>q;
q.push(e);
vis[e] = 1;
while (!q.empty())
{
int t = q.front();
q.pop();
for (int s = head[t]; ~s; s = ed[s].ne)
{
if (d[ed[s].to] > d[t] + ed[s].len)
{
d[ed[s].to] = d[t] + ed[s].len;
if (!vis[ed[s].to])
{
vis[ed[s].to] = 1;
q.push(ed[s].to);
}
}
}
vis[t] = 0;
}
}
int main()
{
while (cin >> n >> m)
{
cnt = 0;
init();
for (int s = 0; s < m; s++)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
spfa(1,d); //正向遍历
spfa(n, d2); //反向遍历
int ans = inf;
for (int s = 1; s <= n; s++) //找到次短路~~
{
for (int t = head[s]; ~t; t = ed[t].ne)
{
int a = ed[t].to;
int le = ed[t].len;
int te = d[s] + d2[a] + le;
if (te > d[n] && ans > te)
{
ans = te;
}
}
}
cout << ans << endl;
}
return 0;
} 11 .最大流的Dinic算法~~
#include <string.h>
#include <queue>
using namespace std;
int const inf = 0x3f3f3f3f;
int const MAX = 205;
int n, m;
int c[MAX][MAX], dep[MAX];//dep[MAX]代表当前层数
int bfs(int s, int t)//重新建图，按层次建图
{
queue<int> q;
while(!q.empty())
q.pop();
memset(dep, -1, sizeof(dep));
dep[s] = 0;
q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
for(int v = 1; v <= m; v++){
if(c[u][v] > 0 && dep[v] == -1){//如果可以到达且还没有访问，可以到达的条件是剩余容量大于0，没有访问的条件是当前层数还未知
dep[v] = dep[u] + 1;
q.push(v);
}
}
}
return dep[t] != -1;
}
int dfs(int u, int mi, int t)//查找路径上的最小流量
{
if(u == t)
return mi;
int tmp;
for(int v = 1; v <= m; v++){
if(c[u][v] > 0 && dep[v] == dep[u] + 1 && (tmp = dfs(v, min(mi, c[u][v]), t))){
c[u][v] -= tmp;
c[v][u] += tmp;
return tmp;
}
}
return 0;
}
int dinic()
{
int ans = 0, tmp;
while(bfs(1, m)){
while(1){
tmp = dfs(1, inf, m);
if(tmp == 0)
break;
ans += tmp;
}
}
return ans;
}
int main()
{
while(~scanf("%d %d", &n, &m)){
memset(c, 0, sizeof(c));
int u, v, w;
while(n--){
scanf("%d %d %d", &u, &v, &w);
c[u][v] += w;
}
printf("%d\n", dinic());
}
return 0;
} 12.树状数组的区间修改~单点查询~
#include<iostream>
#include<cstdio>
using namespace std;
int c[100005];
int n;
int lowbit(int x)
{
return x&(-x);
}
void updata(int x,int d)
{
for (int s = x; s > 0; s -= lowbit(s))
{
c[s] += d;
}
}
int getn(int x)
{
int ans = 0;
for (int s = x; s <= n; s += lowbit(s))
{
ans += c[s];
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
while (cin >> n&&n)
{
memset(c, 0, sizeof(c));
int k = n;
while (k--)
{
int a, b;
cin >> a >> b;
updata(a-1, -1);
updata(b, 1);
}
for (int s = 1; s <= n; s++)
{
if (s != n)
{
cout << getn(s) << " ";
}
else
{
cout << getn(s) << endl;
}
}
}
return 0;
}
13. 树状数组的区间查询区间修改~~
#include<iostream>
#include<cstdio>
using namespace std;
long long int c[100005][2] = { 0 };
int n, q;
int lowbit(int x)
{
return x&(-x);
}
void add(int pos, int x,int f)
{
while (pos <= n)
{
c[pos][f] += x;
pos += lowbit(pos);
}
}
long long qu(int pos, int f)
{
long long res = 0;
while (pos > 0)
{
res += c[pos][f];
pos -= lowbit(pos);
}
return res;
}
long long ask(int pos)
{
long long res = (pos + 1)*qu(pos, 0) - qu(pos, 1);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin >> n;
int a = 0, b, opt, x;
for (int s = 1; s <= n; s++)
{
cin >> b;
add(s, b - a, 0);
add(s, (b - a)*s, 1);
a = b;
}
cin >> q;
for (int s = 1; s <= q; s++)
{
cin >> opt;
if (opt == 1) //1的时候是修改~
{
cin >> a >> b >> x;
add(a, x, 0);
add(b + 1, -x, 0);
add(a, x*a, 1);
add(b + 1, -x*(b + 1), 1);
}
else if (opt == 2)
{
cin >> a >> b;
cout << ask(b) - ask(a - 1) << endl;
}
}
return 0;
} 14.割点的判断
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct ***
{
int to, ne;
}es[10005];
int head[100];
int e;
void add(int u, int v)
{
es[e].to = v;
es[e].ne = head[u];
head[u] = e++;
}
int root;
int ans;
int dfn[105];
int low[105];//最早返祖节点；
int vis[105];
int ar[105];
int time;
void tarjan(int u, int fa)
{
int son = 0; //子孙数量
vis[u] = 1;//标记已经被访问过
dfn[u] = low[u] = ++time;
for (int s = head[u]; ~s; s = es[s].ne)
{
int v = es[s].to;//找到子孙节点；
if (!vis[v])//如果这个不是曾经的祖宗
{
tarjan(v, u);//遍历
son++;//子孙++
low[u] = min(low[u], low[v]);//如果子孙能够回溯到更早的~~那么父亲辈的他也行~~
if (u == root&&son > 1 || u != root&&dfn[u] <= low[v])//如之前所言~
{
ar[u] = 1;
}
}
if (vis[v] && v != fa)
{
low[u] = min(low[u], dfn[v]);
}
}
}
int main()
{
int n;
while (~scanf("%d", &n) && n)
{
memset(vis, 0, sizeof(vis));
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low));
memset(ar, 0, sizeof(ar));
e = 0;
time = 0;
ans = 0;
int u, v;
while (scanf("%d", &u) && u)
{
while (getchar() != '\n')
{
scanf("%d", &v);
add(u, v);
add(v, u);
}
}
root = 1;
tarjan(root, -1);
int ans=0;
for (int s = 1; s <= n; s++)
{
if (ar[s])
{
ans++;
}
}
cout << ans << endl;
}
return 0;
} 15. 算重边的次小生成树~~
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int n, m;
struct node
{
int u, v, cost;
}e[121211];
int pre[121211];
int edge[112211];
bool cmp(struct node a, struct node b)
{
return a.cost<b.cost;
}
int Find(int a)
{
if (a != pre[a])
{
pre[a] = Find(pre[a]);
}
return pre[a];
}
int top;
int Kru()
{
int num = 0;
for (int i = 0; i <= n; i++)
pre[i] = i;
for (int i = 0; i<m; i++)
{
int x = Find(pre[e[i].u]);
int y = Find(pre[e[i].v]);
if (x != y)
{
num += e[i].cost;
edge[++top] = i;
pre[y] = x;
}
}
int k = 0;
for (int i = 1; i <= n; i++)
{
if (pre[i] == i)
k++;
}
if (k == 1)
return num;
else
return INF;
}
//int top;
int Kru2(int xx)
{
int num = 0;
for (int i = 0; i <= n; i++)
pre[i] = i;
for (int i = 0; i<m; i++)
{
if (i == xx)
continue;
int x = Find(pre[e[i].u]);
int y = Find(pre[e[i].v]);
if (x != y)
{
num += e[i].cost;
// edge[++top] = i;
pre[y] = x;
}
}
int k = 0;
for (int i = 1; i <= n; i++)
{
if (pre[i] == i)
k++;
}
if (k == 1)
return num;
else
return INF;
}
int main()
{
int T;
scanf("%d", &T);
for (int t = 1; t <= T; t++)
{
scanf("%d %d", &n, &m);
for (int i = 0; i<m; i++)
{
scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].cost);
}
sort(e, e + m, cmp);
top = -1;
int ans1 = Kru(), ans2 = INF;
for (int i = 0; i <= top; i++)
{
int x = edge[i];
ans2 = min(ans2, Kru2(x));
}
if (ans1 == INF)
printf("Case #%d : No way\n", t);
else if (ans2 == INF)
printf("Case #%d : No second way\n", t);
else
printf("Case #%d : %d\n", t, ans2);//次小生成树的长短~
}
return 0;
} 16 .无向图（可化为有向图）的最小环求法（至少3点）
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define inf 10000000
int n, m, a, b, c;//注意这里不能用0x3f3f3f3f!!因为可能连续3个inf相加~~超出int范围
int map[105][105];//来储存边的长度；
int A[105][105];//a到b的最短边；
int floyd()
{
int minn = inf;
for (int s = 1; s <= n; s++)
{
for (int e = 1; e < s; e++)
{
for (int w = e + 1; w < s; w++)
{
int t = A[e][w] + map[e][s] + map[s][w];//点至少为3的环~~至于为什么用map~是因为用最小A的情况下可能会重复路径
if (t < minn)
{
minn = t;
}
}
}
for (int e = 1; e <= n; e++)
{
for (int w = 1; w <= n; w++)
{
if (A[e][w] > A[e][s] + A[s][w])
{
A[e][w] = A[e][s] + A[s][w];//更新~
}
}
}
}
return minn;
}
int main()
{
while (cin >> n >> m)
{
for (int s = 1; s <= n; s++)
{
for (int e = 1; e <= n; e++)
{
map[s][e] = A[s][e] = inf;//初始化
}
}
for (int s = 1; s <= m; s++)
{
cin >> a >> b >> c;
map[a][b] = map[b][a] = A[a][b] = A[b][a] = min(map[a][b], c);//建图
}
int ans = floyd();
if (ans == inf)
{
cout << "It's impossible.\n";
}
else
{
cout << ans << endl;
}
}
return 0;
}
17. KM算法~~
#include <stdio.h>
#include <string.h>
#define M 310
#define inf 0x3f3f3f3f
int n,nx,ny;
int link[M],lx[M],ly[M],slack[M]; //lx,ly为顶标，nx,ny分别为x点集y点集的个数
int visx[M],visy[M],w[M][M];
int DFS(int x)
{
visx[x] = 1;
for (int y = 1;y <= ny;y ++)
{
if (visy[y])
continue;
int t = lx[x] + ly[y] - w[x][y];
if (t == 0) //
{
visy[y] = 1;
if (link[y] == -1||DFS(link[y]))
{
link[y] = x;
return 1;
}
}
else if (slack[y] > t) //不在相等子图中slack 取最小的
slack[y] = t;
}
return 0;
}
int KM()
{
int i,j;
memset (link,-1,sizeof(link));
memset (ly,0,sizeof(ly));
for (i = 1;i <= nx;i ++) //lx初始化为与它关联边中最大的
for (j = 1,lx[i] = -inf;j <= ny;j ++)
if (w[i][j] > lx[i])
lx[i] = w[i][j];
for (int x = 1;x <= nx;x ++)
{
for (i = 1;i <= ny;i ++)
slack[i] = inf;
while (1)
{
memset (visx,0,sizeof(visx));
memset (visy,0,sizeof(visy));
if (DFS(x)) //若成功（找到了增广轨），则该点增广完成，进入下一个点的增广
break; //若失败（没有找到增广轨），则需要改变一些点的标号，使得图中可行边的数量增加。
//方法为：将所有在增广轨中（就是在增广过程中遍历到）的X方点的标号全部减去一个常数d，
//所有在增广轨中的Y方点的标号全部加上一个常数d
int d = inf;
for (i = 1;i <= ny;i ++)
if (!visy[i]&&d > slack[i])
d = slack[i];
for (i = 1;i <= nx;i ++)
if (visx[i])
lx[i] -= d;
for (i = 1;i <= ny;i ++) //修改顶标后，要把所有不在交错树中的Y顶点的slack值都减去d
if (visy[i])
ly[i] += d;
else
slack[i] -= d;
}
}
int res = 0;
for (i = 1;i <= ny;i ++)
if (link[i] > -1)
res += w[link[i]][i];
return res;
}
int main ()
{
int i,j;
while (scanf ("%d",&n)!=EOF)
{
nx = ny = n;
// memset (w,0,sizeof(w));
for (i = 1;i <= n;i ++)
for (j = 1;j <= n;j ++)
scanf ("%d",&w[i][j]);
int ans = KM();
printf ("%d\n",ans);
}
return 0;
} 18 . 字典树~求一堆数里面有多少所求前缀
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
int tree[200001][26], cnt, sum[200001];
int n, m;
string s;
void insert()
{
int len = s.length();
int rt = 0;
for (int i = 0; i<len; i++)
{
int id = s[i] - 'a';//这个节点的儿子~
if (!tree[rt][id])//如果没有出现过~
{
tree[rt][id] = ++cnt;//创造一个~
}
sum[tree[rt][id]]++;//某个匹配成功的前缀数量是下个位置的sum~
rt = tree[rt][id];//进位~进入下个节点
}
}
int search()
{
int rt = 0;
int len = s.length();
for (int i = 0; i<len; i++)
{
int id = s[i] - 'a';
if (!tree[rt][id]) return 0;//此时匹配失败~返0退出
rt = tree[rt][id];//否则继续进位查找
}//rt经过此循环后变成前缀最后一个字母所在位置的后一个位置
return sum[rt];//因为前缀后移了一个保存，所以此时的sum[rt]就是要求的前缀出现的次数
}
void init()
{
memset(tree, 0, sizeof(tree));
memset(sum, 0, sizeof(sum));
}
int main()
{
init();
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
cin >> s;
insert();
}
scanf("%d", &m);
for (int i = 1; i <= m; i++)
{
cin >> s;
printf("%d\n", search());
}
return 0;
}
19 . 最小费用最大流~
#include<bits/stdc++.h>
using namespace std;
//最小费用最大流，求最大费用只需要取相反数，结果取相反数即可。
//点的总数为 N，点的编号 0~N-1
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{
N = n;
tol = 0;
memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)
{
edge[tol].to = v;
edge[tol].cap = cap;
edge[tol].cost = cost;
edge[tol].flow = 0;
edge[tol].next = head[u];
head[u] = tol++;
edge[tol].to = u;
edge[tol].cap = 0;
edge[tol].cost = -cost;
edge[tol].flow = 0;
edge[tol].next = head[v];
head[v] = tol++;
}
bool spfa(int s,int t)
{
queue<int>q;
for(int i = 0; i < N; i++)
{
dis[i] = INF;
vis[i] = false;
pre[i] = -1;
}
dis[s] = 0;
vis[s] = true;
q.push(s);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = false;
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].to;
if(edge[i].cap > edge[i].flow &&
dis[v] > dis[u] + edge[i].cost )
{
dis[v] = dis[u] + edge[i].cost;
pre[v] = i;
if(!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if(pre[t] == -1)return false;
else return true;
}
//返回的是最大流，cost存的是最小费用
int minCostMaxflow(int s,int t,int &cost)
{
int flow = 0;
cost = 0;
while(spfa(s,t))
{
int Min = INF;
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
if(Min > edge[i].cap - edge[i].flow)
Min = edge[i].cap - edge[i].flow;
}
for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])
{
edge[i].flow += Min;
edge[i^1].flow -= Min;
cost += edge[i].cost * Min;
}
flow += Min;
}
return flow;
}
20 . 倍增的lca算法~
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=230100;
const int DEG=20;
struct ***
{
int to,ne,len;
}ed[maxn*2];
int head[maxn],cnt;
int dis[maxn];//计算距离；
void add(int u,int v,int w)
{
ed[cnt].to=v;
ed[cnt].len=w;
ed[cnt].ne=head[u];
head[u]=cnt++;
}
void init()
{
cnt=1;
memset(head,-1,sizeof(head));
memset(dis,0,sizeof(dis));
}
int fa[maxn][DEG];
int deg[maxn];//深度数组
void BFS(int root)
{
queue<int>q;
deg[root]=0;
fa[root][0]=root;
q.push(root);
dis[root]=0;//
while(!q.empty())
{
int t=q.front();
q.pop();
for(int s=1;s<DEG;s++)
{
fa[t][s]=fa[fa[t][s-1]][s-1];
}
for(int s=head[t];s!=-1;s=ed[s].ne)
{
int v=ed[s].to;
if(v==fa[t][0])
{
continue;
}
deg[v]=deg[t]+1;
dis[v]=dis[t]+ed[s].len;//
fa[v][0]=t;
q.push(v);
}
}
}
int LCA(int u,int v)
{
if(deg[u]>deg[v])
{
swap(u,v);
}
int hu=deg[u],hv=deg[v];
int tu=u,tv=v;
for(int det=hv-hu,s=0;det;det>>=1,s++)
{
if(det&1)
{
tv=fa[tv][s];
}
}
if(tu==tv)
{
return tu;
}
for(int s=DEG-1;s>=0;s--)
{
if(fa[tu][s]==fa[tv][s])
{
continue;
}
tu=fa[tu][s];
tv=fa[tv][s];
}
return fa[tu][0];
}
bool in[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);//一般图都是n-1个边的；这里用m代替；
init();
memset(in,0,sizeof(in));
for(int s=1;s<=m;s++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);//这里c是指有边权的lca~来求关于lca的距离的操作的
add(a,b,c);
add(b,a,c);
in[b]=1;
}
int root;
for(int s=1;s<=n;s++)
{
if(!in[s])
{
root=s;
break;
}
}
BFS(root);
int te;
cin>>te;
while(te--)
{
int u,v;
scanf("%d%d",&u,&v);
// cout<<LCA(u,v)<<endl;
cout<<dis[u]+dis[v]-2*dis[LCA(u,v)]<<endl;
}
return 0;
}
21. 2-SAT （给定N个组，每个组有两个点，某些点不相容，从每个组选一个点问怎么选出相容的N个点）
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 20000 + 10;
const int maxm = 1e5 + 10;
struct Edge
{
int to, next;
}edge[maxm];
int head[maxn], cnt;
void ini()
{
cnt = 0;
memset(head, -1, sizeof(head));
}
void addedge(int u, int v)
{
edge[cnt].to = v; edge[cnt].next = head[u]; head[u] = cnt++;
}
//染色标记，为true表示选择
bool vis[maxn];
//栈
int S[maxn], top;
bool dfs(int u)
{
//如果u和他的反点被同时选中，那么这个图无解
if (vis[u ^ 1])
return false;
//如果有环且不经过u的反向点，那么该解成立
if (vis[u])
return true;
vis[u] = true;
S[top++] = u;
for (int i = head[u]; i != -1; i = edge[i].next)
{
if (!dfs(edge[i].to))
return false;
}
//u开始的有向路径无环得到一个可行的解
return true;
}
bool Twosat(int n)
{
memset(vis, false, sizeof(vis));
//找字典序最小的解
for (int i = 0; i<n; i += 2)
{
if (vis[i] || vis[i ^ 1])
continue;
top = 0;
//以i为起点选择，如果i的反点在同一个环中，
if (!dfs(i))
{
//回溯
while (top)
vis[S[--top]] = false;
//判定以i的反点开始是否存在可行解
if (!dfs(i ^ 1))
//不存在返回false
return false;
}
}
//整个图存在可行解
return true;
}
int main()
{
int n, m;
int u, v;
while (scanf("%d%d", &n, &m) == 2)
{
ini();
while (m--)
{
scanf("%d%d", &u, &v);
u--, v--;
//从0开始标号，异或值表示反向点或者反向边
addedge(u, v ^ 1);
addedge(v, u ^ 1);
}
//判断该2-sat问题是否有解
if (Twosat(2 * n))
{
for (int i = 0; i< 2 * n; i++)
//字典序最小的解
if (vis[i])
printf("%d\n", i + 1);
}
else printf("NIE\n");
}
return 0;
}
比亚迪工作强度 342人发布
