csp突击图论题目
【csp突击图论题目】//BFS 求第一个点到最后一个点的最短路
#include
using namespace std;
const int N=1e5+10,M=2*N;
int n,m,h[N],e[M],ne[M],idx,d[N];
//n个点m条边
void add(int a,int b){//a和b之间加边
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){
memset(d,-1,sizeof(d));
queue q;
d[1]=0;
q.push(1);
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h[t];
i!=-1;
i=ne[i]){
int j=e[i];
if(d[j]==-1){
d[j]=d[t]+1;
q.push(j);
}
}
}
return d[n];
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof(h));
for(int i=0;
i>a>>b;
add(a,b);
}
cout< //判断有向图是否存在拓扑排序
#include
#include
#include
#include
using namespace std;
const int N = 1e5 + 10;
int e[N],ne[N],h[N],idx,d[N],n,m,top[N],cnt = 1;
// e,ne,h,idx 邻接表模板
void add(int a,int b){// d 代表每个元素的入度
e[idx] = b;
// top是拓扑排序的序列，cnt代表top中有多少个元素
ne[idx] = h[a];
h[a] = idx ++;
}
bool topsort(){
queue q;
int t;
for(int i = 1;
i <= n;
++i)// 将所有入度为0的点加入队列
if(d[i] == 0) q.push(i);
while(q.size()){
t = q.front();
//每次取出队列的首部
top[cnt] = t;
//加入到 拓扑序列中
cnt ++;
// 序列中的元素 ++
q.pop();
for(int i = h[t];
i != -1;
i = ne[i]){// 遍历 t 点的出边
int j = e[i];
d[j] --;
// j 的入度 --
if(d[j] == 0) q.push(j);
//如果 j 入度为0，加入队列当中
}
}
if(cnt < n) return 0;
else return 1;
}
int main(){
int a,b;
cin >> n >> m;
memset(h,-1,sizeof h);
while(m--){
cin >> a >> b;
add(a,b);
d[b] ++;
// a -> b , b的入度++
}
if(topsort() == 0) cout << "-1";
else {
for(int i = 1;
i <= n;
++i){
cout << top[i] <<" ";
}
}
return 0;
}
//迪杰斯特拉求最短路
#include
#include
#include
#include
using namespace std;
typedef pair PII;
const int N=100010;
int h[N],e[N],ne[N],idx,w[N];
int dist[N];
bool st[N];
int n,m;
void add(int a,int b,int c){
e[idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx++;
}
int dijktra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
priority_queue,greater>heap;
heap.push({0,1});
while(heap.size()){
auto t=heap.top();
heap.pop();
int ver=t.second,distance=t.first;
if(st[ver])continue;
for(int i=h[ver];
i!=-1;
i=ne[i]){
int j=e[i];
if(dist[j]>distance+w[i]){
dist[j]=distance+w[i];
heap.push({dist[j],j});
}
}
}
if(dist[n]==0x3f3f3f3f)return -1;
return dist[n];
}int main(){
memset(h,-1,sizeof h);
cin>>n>>m;
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
}
cout< //有边数限制的最短路
#include
#include
#include
using namespace std;
const int N = 510, M = 10010;
int n, m, k;
int dist[N], backup[N];
struct Edge{
int a, b, w;
}edges[M];
int bellman_ford(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for (int i = 0;
i < k;
i ++ ){
memcpy(backup, dist, sizeof dist);
for (int j = 0;
j < m;
j ++ ){
int a = edges[j].a, b = edges[j].b, w = edges[j].w;
if (backup[a] != 0x3f3f3f3f && dist[b] > backup[a] + w){
dist[b] = backup[a] + w;
}
}
}
if (dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d%d%d", &n, &m, &k);
for (int i = 0;
i < m;
i ++ ){
int a, b, w;
scanf("%d%d%d", &a, &b, &w);
edges[i] = {a, b, w};
}
int t = bellman_ford();
if (t == -1) puts("impossible");
else printf("%d\n", t);
return 0;
}
//Floyd算法求任意两点最短路
#include
using namespace std;
const int N = 210, M = 2e+10, INF = 1e9;
int n, m, k, x, y, z;
int d[N][N];
void floyd() {
for(int k = 1;
k <= n;
k++)
for(int i = 1;
i <= n;
i++)
for(int j = 1;
j <= n;
j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
int main() {
cin >> n >> m >> k;
for(int i = 1;
i <= n;
i++)
for(int j = 1;
j <= n;
j++)
if(i == j) d[i][j] = 0;
else d[i][j] = INF;
while(m--) {
cin >> x >> y >> z;
d[x][y] = min(d[x][y], z);
//注意保存最小的边
}
floyd();
while(k--) {
cin >> x >> y;
if(d[x][y] > INF/2) puts("impossible");
//由于有负权边存在所以约大过INF/2也很合理
else cout << d[x][y] << endl;
}
return 0;
}
//求图的最小生成树
#include
using namespace std;
const int N=1e5+10,M=2e5+10,INF=0x3f3f3f3f;
int n,m;
int fa[N];
structEdge{
int a,b,w;
bool operator<(const Edge &W)const{return w>n>>m;
for(int i=0;
i>a>>b>>c;
edges[i]={a,b,c};
}
int ans=kruskal();
if(ans==INF)puts("impossible");
else cout< //二分图的最大匹配
二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。
二分图的最大匹配：所有匹配中包含边数最多的一组匹配被称为二分图的最大匹配，其边数即为最大匹配数。
#include
#include
using namespace std;
const int N = 510 , M = 100010;
int n1,n2,m;
int h[N],ne[M],e[M],idx;
bool st[N];
int match[N];
void add(int a , int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void init(){
memset(h,-1,sizeof h);
}
int find(int x){//遍历自己喜欢的女孩
for(int i = h[x] ;
i != -1 ;
i = ne[i]) {
int j = e[i];
if(!st[j]){//如果在这一轮模拟匹配中,这个女孩尚未被预定
st[j] = true;
//那x就预定这个女孩了
if(!match[j]||find(match[j])) {//如果女孩j没有男朋友，
match[j] = x;
//或者她原来的男朋友能够预定其它喜欢的女孩。配对成功
return true;
}
}
}//自己中意的全部都被预定了。配对失败。
return false;
}
int main(){
init();
cin>>n1>>n2>>m;
while(m--) {
int a,b;
cin>>a>>b;
add(a,b);
}
int res = 0;
for(int i = 1;
i <= n1 ;
i ++){//因为每次模拟匹配的预定情况都是不一样的所以每轮模拟都要初始化
memset(st,false,sizeof st);
if(find(i))
res++;
}
cout< 推荐阅读
- 微服务|微服务系列:服务发现与注册-----Eureka(面试突击!你想了解的Eureka都在这里.持续更新中......)
- 庄稼地里的除草突击队
- 面试突击20（进程和线程有什么区别（））
- 面试突击19（为什么ConcurrentHashMap不允许插入null值（））
- 图论算法遍历基础
- 面试突击17（HashMap除了死循环还有什么问题（））
- chrome插件教程5-了解csp网站安全策略
- 面试突击15（说一下HashMap底层实现（及元素添加流程？））
- 图论|POJ1364 King 差分约束
- 图论|tarjan算法之——割点和桥