图论 2023.11.27

本文介绍: 转换为拓扑图：入度为每个窗口不匹配的数量，一旦为0完全匹配，边为该窗口不匹配的字符，编号为(窗口编号i相连字符编号i+j)之后Krusk al先添加必须要的的0边,再以0边优先，把0边添加至k后,再添1边，最后还要检查图的连通性。给定一个它的高度为 h,它的长度和宽度我们可以认为是无限大的奶酪，有n个空洞坐标为（x,y,z）给定一个row行line列大小的矩阵，给定n个boss的位置,需要从左下角，到达右上角。深度优先搜索,不需要回溯，进入和出来判断只需看z-r,z+r和0,h的比较。

Krusk al定义不同的优先级

P3623 [APIO2008] 免费道路
给定一个无向图，其中一些边是0，其他边为1
两个不同的点之间都应该一条且仅由一条边连接
并保持刚好K条0，求是否有解决方案
n<=2e4,m<=1e5
Krusk al定义不同的优先级
思路：Krusk al先以1边优先,筛出必须要的0边
之后Krusk al先添加必须要的的0边,再以0边优先，把0边添加至k后,再添1边，最后还要检查图的连通性

#include <iostream&gt;
#include <cstdlib&gt;
#include <cstdio&gt;
#include <algorithm&gt;
using namespace std;
const int N = 1e6 + 10;
int n, m, k, fa[N], tot, cnt;
struct edge {
    int u, v, w;
}e[N], ans[N];
bool cmp1(edge e1, edge e2) {
    return e1.w > e2.w;
}
bool cmp2(edge e1, edge e2) {
    return e1.w < e2.w;
}
int find(int x) {
    return x == fa[x] ? x:fa[x] = find(fa[x]);
}
void init() {
    cnt = tot = 0;
    for (int i = 1; i <= n; i++) fa[i] = i;
}
void check() {
    int tmp = find(1);
    for (int i = 2; i <= n; i++) {
        int f = find(i);
        if (f != tmp) {
            printf("no solutionn");
            exit(0);
        }
        tmp = f;
    }
}
int main()
{
    cin >> n >> m >> k;
    for (int i = 1; i <= m; i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    init();
    sort(e + 1, e + m + 1, cmp1);     //从大到小(1边优先)
    for (int i = 1; i <= m; i++) {
        int x = find(e[i].u);
        int y = find(e[i].v);
        if (x == y)  continue;
        fa[x] = y;
        if (e[i].w == 0) {
            tot++, e[i].w = -1;    //定为必须边，下次的Kruskal此边为最高优先级
        }
    }
    if (tot > k) {               //(1边优先)0边>k,0边优先时,0边依然>k
        printf("no solutionn");
        return 0;
    }
    check();
    init(); 
    sort(e + 1, e + m + 1, cmp2);
    for (int i = 1; i <= m; i++) {
        int f1 = find(e[i].u), f2 = find(e[i].v);
        if (f1 == f2) continue;
        if (e[i].w == 1 || tot < k) {
            fa[f1] = f2;
            if (e[i].w < 1) {
                tot++, e[i].w = 0;
            }
            ans[++cnt] = e[i];
        }
    }
    if (tot < k) {
        printf("no solutionn");
        return 0;
    }
    check();
    for (int i = 1; i <= cnt; i++) {
        printf("%d %d %dn", ans[i].u, ans[i].v, ans[i].w);
    }
    return 0;
}

几何联通

P3958 [NOIP2017 提高组] 奶酪
给定一个它的高度为 h,它的长度和宽度我们可以认为是无限大的奶酪，有n个空洞坐标为（x,y,z）
统一半径为r，能否利用已有的空洞跑到奶酪的上表面去
深度优先搜索,不需要回溯，进入和出来判断只需看z-r,z+r和0,h的比较
n<=1e3,h,r<=1e9

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstring>
#include<math.h>
using namespace std;
const int N = 1e3 + 10;
int n;
double h, r;
int vis[N];
int ans;
struct cir {
    double x, y, z;
    bool operator <(const cir& c)const { //按从低到高
        return z < c.z;                           
    }
}a[N];
double dist(double x1, double y1, double z1, double x2, double y2, double z2){
    return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) + (z2 - z1) * (z2 - z1));
}
void dfs(int now) {
    if (ans) return;
    if (a[now].z + r>= h) {
        ans = 1;
        return;
    }
    vis[now] = 1;
    for (int i = 1; i <= n; i++) {
        if (vis[i])  continue;
        if (dist(a[now].x, a[now].y, a[now].z, a[i].x, a[i].y, a[i].z) > 2 * r) continue;
        dfs(i);
    }
}
void solve() {
    memset(vis, 0, sizeof(vis));
    ans = 0;
    cin >> n >> h >> r;
    for (int i = 1; i <=n; i++) {
        cin >> a[i].x >> a[i].y >> a[i].z;
    }
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        if (a[i].z- r <= 0) {
            dfs(i);    //深搜
        }
    }
    if (!ans) {
        cout << "No" << 'n';
    }
    else {
        cout << "Yes" << 'n';
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)  solve();
}

二维联通

P2498[SDOI2012] 拯救小云公主
给定一个row行line列大小的矩阵，给定n个boss的位置,需要从左下角，到达右上角
找一条路径使到距离boss的最短距离最远,输出最远距离
n<=3000
思路：小数二分最远距离,boss点作为圆心, 参考奶酪
左边界或上边界通过这些洞和右边界或下边界联通时,问题无解

#include<iostream>
#include<cstring>
#include<math.h>
#include<queue>
using namespace std;
int dis[3001][3001];
int x[3001], y[3001];
int getdis(int x1, int y1, int x2, int y2) {
    return pow(x1 - x2, 2) + pow(y1 - y2, 2);
}
bool able(int d, double r) {
    return r * r * 4 > d;
}
int row, line, n;
queue<int>q;
bool vis[3001];
bool bfs(double r) {
    memset(vis, 0, sizeof(vis));
    while (!q.empty())q.pop();
    for (int i = 1; i <= n; i++) {
        if (row - y[i] < r||x[i]<r) {   // 左下角(row, 0)出发通过这些圆
            q.push(i), vis[i] = 1;
        }
    }
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        if (y[p] < r|| line - x[p] < r) {      //右上角(0,line)通过这些圆
            return 0;
        }
        for (int i = 1; i <= n; i++)
            if (!vis[i] && able(dis[p][i], r)) {       
                vis[i] = 1, q.push(i);
            }
    }
    return 1;
}
int main() {
    
    cin >> n >> line >> row;
    line--; row--;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        x[i]--;
        y[i]--;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            dis[i][j] = dis[j][i] = getdis(x[i], y[i], x[j], y[j]);
    double l = 0, r = min(row, line), mid;
    for (int i = 1; i <= 60; i++) {
        mid = (l + r) / 2;
        if (bfs(mid))l = mid;
        else r = mid;
    }
    printf("%.2lfn", l);
    return 0;
}

视为T在S之间滑动，转换为拓扑图目标所有窗口匹配，即度数为0 (atcoder 329 E)

给定一个长度为n字符串S,长度为m的字符串T

将长度为n字符串全是#变成S，操作：用T替换S的部分区间

n<=2e5,m<=5

思路：视为T在S之间滑动，于是有n-m+1的窗口

转换为拓扑图：入度为每个窗口不匹配的数量，一旦为0完全匹配，边为该窗口不匹配的字符，编号为(窗口编号i相连字符编号i+j)

之后拓扑，ans倒序后得到操作的顺序，目标为所有窗口完全匹配因为（视为T在S之间滑动）

#include<bits/stdc++.h>

#include<iostream>

#include<algorithm>

#include<map>

#include<set>

#include<queue>

#include<cstring>

#include<math.h>

#include<map>

#include<vector>

#include<stack>

#include<unordered_map>

#include<unordered_set>

#include<bitset>

#include<array>

using namespace std;



#define endl 'n'



#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)

#define int long long

#define int128 __int128_t

#define ll long long

#define ld long double

typedef unsigned long long ull ;

#define fr(i,l,r) for(int i=l;i<=r;i++)

#define fer(i,x)   for(int i=e.head[x];i;i=e.next[i])

#define ufr(i,n,z) for(int i = n;i >= z; i--)

#define pb(x) push_back(x)

#define all(a) a.begin(),a.end()

#define fi first

#define se second

typedef pair<int,int> pr;

const int N = 1e6+10;

const int mod=998244353,inf=1e18;







int n,m;



int a[N];

map<int,int>mp;

void solve()

{



    cin>>n>>m;

    string s,t;

    cin>>s>>t;

    vector<int>in(n+1,m);

    vector<vector<int>>e(n+1);            //边                        

    queue<int>q;

    for(int i=0;i<n-m+1;i++){

        for(int j=0;j<m;j++){

            if(s[i+j]==t[j]){

                  in[i]--;

                  if(in[i]==0){              //完全与t对应

                    q.push(i);

                  }

            }

            else{

                e[i+j].push_back(i);          

            }

        }

    }

    vector<int>ans;

    while(!q.empty()){

        int u=q.front();

        q.pop();

        ans.push_back(u);

        for(int i=0;i<m;i++){

            if(mp[u+i]){

                continue;

            }

            mp[u+i]=1;

            for(auto it:e[u+i]){

                in[it]--;

                if(in[it]==0){

                    q.push(it);

                }

            }

        }

    }

    reverse(ans.begin(),ans.end());                //每一次操作位置

    if(ans.size()<n-m+1){

         cout<<"No"<<'n';

    }

    else{

        cout<<"Yes"<<'n';

    }

}



signed main()

{

    ios;

    int t=1;

 //   cin>>t;

    while(t--) solve();

    return 0;

}