一流的聊城做网站费用,自贡做响应式网站开发公司,湖州网站制作公司,网站 建设情况目录
前言#xff1a;
题单#xff1a;
P3386 【模板】二分图最大匹配
P1525 [NOIP2010 提高组] 关押罪犯
P3385 【模板】负环
P3371 【模板】单源最短路径#xff08;弱化版#xff09;
SPFA写法
Dij写法#xff1a; P3385 【模板】负环
P5960 【模板】差分约束…目录
前言
题单
P3386 【模板】二分图最大匹配
P1525 [NOIP2010 提高组] 关押罪犯
P3385 【模板】负环
P3371 【模板】单源最短路径弱化版
SPFA写法
Dij写法 P3385 【模板】负环
P5960 【模板】差分约束 P7771 【模板】欧拉路径
文末: 前言
若刚入门图论想做基础图论题请移步CSDN
题单
P3386 【模板】二分图最大匹配
https://www.luogu.com.cn/problem/P3386 交替路 从未匹配点出发依次经过非匹配边匹配边非匹配边……形成的路径 增广路 从非匹配点出发走交替路最后到达另一非匹配点的路径 算法 可以发现增广路的匹配边比交替路的匹配边多一-----可以尽可能找增广路用DFS或者BFS实现当找不到增广路时就得到了最大匹配边 匈牙利算法 男女相亲男选女可占可让可以有女朋友当遍历到的男生的心仪女生有男朋友时如果该男朋友还有其他心仪女生没有对象那么该男朋友会将女朋友让出来并有新的女朋友真渣啊~(* ︿)超小声嘀咕(*3)╭ const int N 505;
const int M 5e4 5;int cnt;
int head[N];
int match[N];//i的男友
int vis[N];int n, m, e;
int ans;struct EDGE
{int v;int next;
}EDGE[/*2 * */M];void add(int u, int v)
{cnt;EDGE[cnt].v v;EDGE[cnt].next head[u];//不是等于cnthead[u] cnt;
}bool dfs(int f)//boyfriend
{for (int i head[f]; i; i EDGE[i].next)//遍历女友{int v EDGE[i].v;if (vis[v])continue;vis[v] 1;if (match[v] 0 || dfs(match[v]/*传的是男友*/)){match[v] f;return 1;}}return 0;
}int main()
{quickio;cin n m e;int u, v;while (e--){cin u v;add(u, v);//add(v, u);//不要建双边只要遍历男友就可以了}for (int i 1; i n; i)//遍历男友{memset(vis, 0, sizeof(vis));if (dfs(i))ans;}cout ans endl;return 0;
}
P1525 [NOIP2010 提高组] 关押罪犯
https://www.luogu.com.cn/problem/P1525 思路 要用到贪心 按边从大到小排序再按顺序往后安排各自的监狱首先最大的怨气的两个人肯定要放在不同的监狱就是不同的集合----要涉及到并查集放相同监狱的有相同的祖先 #include iostream
#include cstring
#include algorithm
#include vector
#include cmath
#include unordered_map
#include unordered_set
#include map
#include set
#include queue
#include stack
#include deque
#include functional
#include climits#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl \nusing namespace std;
typedef long long ll;const int N 2e4 5;
const int M 1e5 5;int n, m;
int fa[N * 2];// n的存的是敌人struct zf
{int a;int b;int c;
}zf[M];bool cmp(struct zf a, struct zf b)
{return a.c b.c;
}int find(int x)
{if (fa[x] x)return x;return fa[x] find(fa[x]);
}int FindMin()
{for (int i 0; i m; i){int x find(zf[i].a);int y find(zf[i].b);if (x y)return zf[i].c;fa[fa[zf[i].a]]/*注意是fa[fa[]],要把祖先直接归并到敌人集合而不只是自己*/ find(zf[i].b n)/*不是fa[zf[i].b n],因为要找的是最上面的祖先*/;fa[fa[zf[i].b]] find(zf[i].a n);}return 0;
}int main()
{cin n m;//并查集基本操作初始化父亲for (int i 1; i 2 * n; i)fa[i] i;for (int i 0; i m; i){cin zf[i].a zf[i].b zf[i].c;}sort(zf, zf m, cmp);int ans 0;ans FindMin();cout ans endl;return 0;
}
P3385 【模板】负环
https://www.luogu.com.cn/problem/P3385 注意 该题不可以用Dijkstra,只能用SPFA但是通常求最短路最好用Dijkstra,因为SPFA经常被卡例如你可以做这两个题目 ......~(▽)~* 【模板】单源最短路径弱化版 - 洛谷 【模板】单源最短路径标准版 - 洛谷 你会发现SPFA的代码可以过弱化版但是过标准版会有一堆TLE(我会在后面公布这两题的答案ฅʕ•̫͡•ʔฅ) P3371 【模板】单源最短路径弱化版
【模板】单源最短路径弱化版 - 洛谷
SPFA写法
//SPFA
//该代码是可以判断负环的SPFA且采用vector存边#include iostream
#include cstring
#include algorithm
#include vector
#include cmath
#include unordered_map
#include unordered_set
#include map
#include set
#include queue
#include stack
#include deque
#include functional
#include climits#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl \nusing namespace std;
typedef long long ll;const int N 5e5 5;struct edge
{int v;int w;
};
int vis[N];//标记是否在队内所有pop后要置为0和Dij不一样Dij是标记该点访问过不再访问
int ans[N];
int countt[N];//经过每个点的次数如果有一个点的次数 n则有负环vectoredgee[N];int n, m, s;bool SPFA(int s)
{queueintque;//memset(ans, 0x3f, sizeof(ans));该题初始化为这个不够0x3f3f3f3f INT_MAX要初始化为INT_MAX//注意题目要求啊若不能到达则输出 2^31 - 1for (int i 1; i n; i)ans[i] INT_MAX;ans[s] 0;que.push(s);vis[s] 1;while (!que.empty()){int dian que.front();que.pop();vis[dian] 0;/*出队是0注意vis是表示是否在队内的*/for (auto ed : e[dian]){int v ed.v;int w ed.w;if (ans[v] ans[dian] w){ans[v] ans[dian] w;countt[v] countt[dian] 1;if (countt[v] n)return true;//返回true表示有负环if (vis[v] 0){vis[v] 1;que.push(v);}}}}return false;
}int main()
{cin n m s;int u, v, w;for (int i 0; i m; i){cin u v w;e[u].push_back({ v, w });}SPFA(s);for (int i 1; i n; i)cout ans[i] ;return 0;
}
Dij写法 问题 弱化版的代码超时----要用堆优化 (ง •_•)ง核心 priority_queue pairint,int 用优先队列来取最近的点就不用遍历找点了 在priority_queue中是按pair的第一个元素first由大到小排序的所以pair距离点号注意因为要的是最小值所以距离要存负值 (重点敲黑板哦~~ ) 总结 要优先队列来方便选出最短路径注意堆优化优先队列中的排序是从大到小所以存距离要存负数 要一个结构体存每个点的数据head数组存每条链的数据还要用ans数组记录从起点到某点的最短距离用vis数组记录点是否被加入过最短路径避免重复加入 #include queue
/*堆优化利用优先队列降低复杂度直接排序注意优先队列是由大到小排列的,因此距离是负数 */
#include climits
#include iostreamusing namespace std;const int MAX 1e6;
int n, m, s;
int ans[MAX];//最短距离
int cnt;
int head[MAX];//出边的头标记
int visit[MAX];//标记该点是否被访问过struct EDGE
{int to;int next;//下一个出边int wei;//权值
}edge[MAX];void add(int u, int v, int w)
{cnt;edge[cnt].wei w;edge[cnt].to v;edge[cnt].next head[u];head[u] cnt;
}int main()
{int i;int u, v, w;cin n m s;for (i 1; i n; i)ans[i] INT_MAX;ans[s] 0;for (i 1; i m; i){cin u v w;add(u, v, w);}priority_queuepairint, int que;//距离点que.push({0, s});while (!que.empty()){int qh que.top().first;int h que.top().second;que.pop();/*记得pop()!!!!!!!!!*/if (visit[h] 0){visit[h] 1;for (i head[h]; i ! 0; i edge[i].next)//不断找下一个儿子直到找完{if (ans[edge[i].to] ans[h] edge[i].wei){ans[edge[i].to] ans[h] edge[i].wei;if (visit[edge[i].to] 0)que.push({ -ans[edge[i].to], edge[i].to });}}}}for (i 1; i n; i)cout ans[i] ;cout endl;return 0;
} P3385 【模板】负环
P3385 【模板】负环 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
//负环
//该代码是可以判断负环的SPFA且采用vector存边const int N 5e5 5;struct edge
{int v;int w;
};
int vis[N];//标记是否在队内所有pop后要置为0和Dij不一样Dij是标记该点访问过不再访问
int ans[N];
int countt[N];//经过每个点的次数如果有一个点的次数 n则有负环vectoredgee[N];int n, m, s;bool SPFA(int s)
{queueintque;for (int i 1; i n; i)ans[i] INT_MAX;memset(vis, 0, sizeof(vis));memset(countt, 0, sizeof(countt));ans[s] 0;que.push(s);vis[s] 1;while (!que.empty()){int dian que.front();que.pop();vis[dian] 0;/*出队是0注意vis是表示是否在队内的*/for (auto ed : e[dian]){int v ed.v;int w ed.w;if (ans[v] ans[dian] w){ans[v] ans[dian] w;countt[v] countt[dian] 1;if (countt[v] n)return true;//返回true表示有负环if (vis[v] 0){vis[v] 1;que.push(v);}}}}return false;
}int main()
{int t;cin t;while (t--){memset(e, 0, sizeof(e));cin n m;int u, v, w;for (int i 0; i m; i){cin u v w;if (w 0){e[u].push_back({ v, w });e[v].push_back({ u, w });}elsee[u].push_back({ v, w });}if (SPFA(1)){cout YES endl;}elsecout NO endl;}return 0;
}
P5960 【模板】差分约束
【模板】差分约束 - 洛谷 一个差分约束系统是这样的 给出 n 个变量和 m 个约束条件形如 Xi - Xj≤Ck 你需要求出一组解使得所有约束条件均被满足。 怎样解这个差分约束系统呢我们将上面的不等式变形一下 Xi≤XjCk (_)? 容易发现这个形式和最短路中的三角形不等式Dis(v)≤Dis(u)w 非常相似。 因此我们就将这个问题转化为一个求最短路的问题比如对于上面这个不等式 1、我们从 j 向 i 连一条权值为 Ck 的边。 2、我们再新建一个 0 号点从 0 号点向其他所有点连一条权值为 0的边。 这个操作相当于新增了一个变量 X0 和 n 个约束条件xi≤x0从而将所有变量都和X0 这一个变量联系起来。 3、然后以 0号点为起点用 SPFA 跑最短路。 如果有负权环差分约束系统无解。否则设从 0号点到 i号点的最短路为 Dis(i)则xiDis(i) 即为差分约束系统的一组可行解。 const int N 5e5 5;struct edge
{int v;int w;
};
int vis[N];//标记是否在队内所有pop后要置为0和Dij不一样Dij是标记该点访问过不再访问
int ans[N];
int countt[N];//经过每个点的次数如果有一个点的次数 n则有负环vectoredgee[N];int n, m, s;bool SPFA(int s)
{queueintque;for (int i 1; i n; i)ans[i] INT_MAX;memset(vis, 0, sizeof(vis));memset(countt, 0, sizeof(countt));ans[s] 0;que.push(s);vis[s] 1;while (!que.empty()){int dian que.front();que.pop();vis[dian] 0;/*出队是0注意vis是表示是否在队内的*/for (auto ed : e[dian]){int v ed.v;int w ed.w;if (ans[v] ans[dian] w){ans[v] ans[dian] w;countt[v] countt[dian] 1;if (countt[v] n 1/*注意这里是n 1了因为多加了一个0号节点*/)return true;//返回true表示有负环if (vis[v] 0){vis[v] 1;que.push(v);}}}}return false;
}int main()
{memset(e, 0, sizeof(e));cin n m;int u, v, w;for (int i 0; i m; i){cin u v w;//e[u].push_back({ v, w });e[v].push_back({ u, w });//注意这里的起点和终点}for (int i 1; i n; i)e[0].push_back({ i, 0 });//注意要让一点可以到达所有点才行但是图内不一定存在这种点所以可以自己创建一个0节点并和所有点都连起来同时边权为0if (SPFA(0) false)//从0号节点出发求它到所有点的最短路径如果有负环该差分约束无解{for (int i 1; i n; i)cout ans[i] ;cout endl;}elsecout NO endl;return 0;
} P7771 【模板】欧拉路径
https://www.luogu.com.cn/problem/P7771 欧拉路径 只经过一次的边 欧拉回路 经过欧拉路径能回到起点的回路 欧拉图 有欧拉 回路 的图 半欧拉图 有欧拉 路径 的图但是没有欧拉 回路 判断是否有欧拉路径1、有向图 欧拉路径 只有两个点出度不等于入度起点出度 入度 1终点入度 出度 1 其他点入度 出度 (﹃)~zZ 欧拉回路 所有点入度等于出度 O_O 2、无向图 欧拉路径 只有两个点的度数为奇数起点出度 入度 1终点入度 出度 1 其他点度数为偶数 (っ´Ι)っ偶数 欧拉回路 所有点度数为偶数 ( ´)(._.) const int N 1e5 5;
const int M 2e5 5;//用Dij不好排序用vector的图
//struct EDGE
//{
// int v;
// int w;
// int next;
//}EDGE[M];
//
//int head[N];
//int ans[N];
//int vis[N];
//int cnt;
//
//int du[N][2];//入度出度
//
//void add(int u, int v, int w)
//{
// cnt;
// EDGE[cnt].v v;
// EDGE[cnt].w w;
// EDGE[cnt].next head[u];
// head[u] cnt;
//}vectorintG[N];
stackintst;
int du[N][2];//入度出度
int cnt[2];//记录多少点出度不等于入度cnt[0]:入度 出度,cnt[1]:出度 入度
int beginn[N];//记录每个点遍历到了哪个出边void DFS(int qi)
{for (int i beginn[qi]; i G[qi].size(); i beginn[qi]/*注意不是i,因为经过DFS后beginn[qi]的值可能早已改变不能再从目前点的后一个点继续走*/){beginn[qi] i 1;DFS(G[qi][i]);}st.push(qi);//最后放因为栈是先进后出要先把该点的出边都遍历完再放入该点以便输出时该点先输出
}int main()
{int n, m;cin n m;int u, v;for (int i 0; i m; i){cin u v;G[u].push_back(v);du[u][1];du[v][0];}int qi 1;//起点//int flag 0;//flag 0表示所有点入度 出度for (int i 1; i n; i){sort(G[i].begin(), G[i].end());//注意vector和数组对sort的用法不同if (du[i][0] ! du[i][1]){//flag 1;if (du[i][0] - du[i][1] 1)//入度 - 出度 1终点{cnt[1];}else if (du[i][1] - du[i][0] 1)//出度 - 入度 1起点{cnt[0];qi i;}else{cout No endl;return 0;}}}if (cnt[0] ! cnt[1]/*起点数不等于终点数*/){cout No endl;return 0;}if (cnt[0] ! 0/*不是欧拉路径*/ cnt[0] ! 1/*不止一个起点*/){cout No endl;return 0;}DFS(qi);while (!st.empty()){cout st.top() ;st.pop();}return 0;
} 文末:
单源最短路径弱化版
【模板】单源最短路径弱化版 - 洛谷
该题可用Dij也可用SPFA该题SPFA可以 单源最短路径标准版
【模板】单源最短路径标准版 - 洛谷
该题只能Dij,若为SPFA 综上所述最好用Dij算法求单源最短路径但若有负边权只能用SPFA
