ACM-ICPC板子

List list的erase(iterato'pos) 会返回下一个元素迭代器的位置，若在end-1(end 无数字)的位置会返回end迭代器即L.size() 其中只需要保证it的正确性即可！

STL 中有用于操作迭代器的三个函数模板，它们是： advance(p, n)：使迭代器 p 向前或向后移动 n 个元素。 distance(p, q)：计算两个迭代器之间的距离，即迭代器 p 经过多少次 + + 操作后和迭代器 q 相等。如果调用时 p 已经指向 q 的后面，则这个函数会陷入死循环。 iter_swap(p, q)：用于交换两个迭代器 p、q 指向的值。

//最终于版本!
#pragma comment(linker, "/STACK:102400000,102400000") 手动扩栈空间！

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e5 + 9;
int a[N];
list<int> L;
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]), L.emplace_back(a[i]);
    int ans = 0;
    while (1)
    {
        int f = 0;
        for(auto it = L.begin(); it != L.end();)
        {
            if(L.size() <= 1) break;
            auto pre = it,ne = it;
            advance(pre,-1);
            advance(ne,1);
            if(it == L.begin()) pre = L.end(),pre--;
            auto x = L.end();
            if(it == --x) ne = L.begin();
            if(*it == *ne || *it + *ne == k)
            {
                f = 1;
                ans++;
                L.erase(it);
                it = L.erase(ne);
            }
            else if(*it == *pre || *it + *pre == k)
            {
                f = 1;
                ans++;
                L.erase(pre);
                it = L.erase(it);
            }
            else it++;
        }
        if(f == 0) break;
    }
    cout<<ans<<"\n";
    return 0;
}

数位dp
ll dfs(ll pos,ll limit,ll num,int x,int has_zero)
{
    //printf("pos = %lld\n",pos);
    if(!limit && ~dp[pos][num][has_zero]) return dp[pos][num][has_zero];
    if(pos == 0) return num;
    int up = limit ? a[pos] : 9;
    ll ans = 0;
    for(int i=0; i<=up; i++)
    {
        ans += dfs(pos - 1,limit && i == up ? 1 : 0,num + (i == x && (has_zero || x != 0)),x,has_zero || i != 0);
    }
    if(!limit) dp[pos][num][has_zero] = ans;
    return ans;
}
 
ll solve(ll n,int x)
{
    memset(dp,-1,sizeof dp);
    ll pos = 0;
    while(n)
    {
        a[++pos] = n % 10;
        n /= 10;
    }
    return dfs(pos,1,0,x,0);
}
cout<<solve(b) - solve(a)<<endl;

分割整行读入字符串
#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    getline(cin , s);
    stringstream ss(s);
    while(ss >> s)
    {
        int a = 0;
        for(int i=0; s[i]; i++) a = a*10 + s[i] - '0';
        cout<<a<<endl;
    }
    return 0;
}

基于主席树的可持久化数组！
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

typedef long long ll;
const int N = 1e6+9;
int a[N],root[N];
int tot;

struct SegmentTree {
    int ls,rs,v;
}tr[N << 5];

int build(int l,int r) {
    int p = ++tot,mid = l + r >> 1;
    if(l == r) {
        tr[p].v = a[l];
        return p;
    }
    tr[p].ls = build(l,mid);
    tr[p].rs = build(mid+1,r);
    return p;
}

int update(int p,int l,int r,int x,int val) {
    int q = ++tot;
    tr[q] = tr[p];
    if(l == r) {
        tr[q].v = val;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].ls = update(tr[q].ls,l,mid,x,val);
    else tr[q].rs = update(tr[q].rs,mid+1,r,x,val);
    return q;
}

int query(int q,int l,int r,int k) {
    if(l == r) {
        return tr[q].v;
    }
    int mid = l + r >> 1;
    if(k <= mid) return query(tr[q].ls,l,mid,k);
    else return query(tr[q].rs,mid+1,r,k);
}

int main() {
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    root[0] = build(1,n);
    for(int i=1; i<=m; i++) {
        int num,op;
        scanf("%d%d",&num,&op);
        if(op == 1) {
            int x,y;
            scanf("%d%d",&x,&y);
            root[i] = update(root[num],1,n,x,y);
        } else {
            int k;
            scanf("%d",&k);
            printf("%d\n",query(root[num],1,n,k));
            root[i] = root[num];
        }
    }
    return 0;
}

主席树 + 离散化
静态区间第k小！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 1e5+9;
int a[N],b[N],root[N],tot;

struct SegmentTree {
    int ls,rs,v;
}tr[N << 5];

void pushup(int u) {
    tr[u].v = tr[tr[u].ls].v + tr[tr[u].rs].v;
}

int build(int l,int r) {
    int p = ++tot,mid = l + r >> 1;
    if(l == r) return p;
    tr[p].ls = build(l,mid);
    tr[p].rs = build(mid+1,r);
    return p;
}

int insert(int p,int l,int r,int x) {
    int q = ++tot;
    tr[q] = tr[p];
    if(l == r) {
        tr[q].v++;
        return q;
    }
    int mid = l + r >> 1;
    if(x <= mid) tr[q].ls = insert(tr[p].ls,l,mid,x);
    else tr[q].rs = insert(tr[p].rs,mid+1,r,x);
    pushup(q);
    return q;
}

int query(int q,int p,int l,int r,int k) {
    if(l == r) return l;
    int cnt = tr[tr[q].ls].v - tr[tr[p].ls].v;
    int mid = l + r >> 1;
    if(k <= cnt) return query(tr[q].ls,tr[p].ls,l,mid,k);
    else return query(tr[q].rs,tr[p].rs,mid+1,r,k - cnt);
}

int main() {
    int n,m;
    cin >> n >> m;
    for(int i=1; i<=n; i++) scanf("%d",&a[i]),b[i] = a[i];
    sort(b+1,b+n+1);
    int len = unique(b+1,b+n+1) - b - 1;
    root[0] = build(1,len);
    for(int i=1; i<=n; i++) {
        int p = lower_bound(b+1,b+len+1,a[i]) - b;
        root[i] = insert(root[i-1],1,len,p);
    }
    while(m--) {
        int l,r,k;
        scanf("%d%d%d",&l,&r,&k);
        printf("%d\n",b[query(root[r],root[l-1],1,len,k)]);
    }
    return 0;
}
作者：我木jj我怕谁
链接：https://www.acwing.com/activity/content/code/content/4211910/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

计算任意多边形的面积！凸凹都可！ 
hdoj2036
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;

struct Point {
    ll x,y;
    Point operator - (Point O)
    {
        return {x - O.x,y - O.y};
    }
} Points[N];

double dot(Point a,Point b) {
    return a.x * b.x + a.y * b.y;
}

double det(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

double area(Point a,Point b,Point c) {
    return det(b - a,c - a);
}

int main() {
    int n;
    while(~scanf("%d",&n),n) {
        for(int i=1; i<=n; i++) {
            ll x,y;
            scanf("%lld%lld",&x,&y);
            Points[i] = {x,y};
        }
        double ans = 0;
        for(int i=2; i<=n-1; i++) {
            ans += area(Points[i],Points[i+1],Points[1]) / 2;
        }
        printf("%.1f\n",ans);
    }
    return 0;
}




//随机数据下凸包上点的个数为log(n)!
OI Wiki旋转卡壳 https://www.luogu.com.cn/problem/P1452
非正解，暴力竟然可以过。。。
凸包上的点远远小于n，所以n方枚举是可以过的要注意在一条边上的时候即：stk[top] == stk[top-1]，特判否则结果是零！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;

struct Point {
    ll x,y;
    Point operator - (Point O) {
        return {x - O.x,y - O.y};
    }
}Points[N],e[N<<1];

bool operator < (Point &a,Point &b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

double get_length(Point a) {
    return sqrt(a.x * a.x + a.y * a.y);
}

double cross(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

double get_dis(Point p,Point a,Point b) {
    Point v1 = b - a,v2 = p - a;
    return fabs(cross(v1,v2) / get_length(v1));
}

ll get_two_dis(Point a,Point b) {
    ll dx = a.x - b.x;
    ll dy = a.y - b.y;
    return (dx * dx + dy * dy);
}

int stk[N];
bool used[N];

double area(Point a,Point b,Point c) {
    return cross(b - a,c - a);
}

double ans;

void andrew(ll &n) {
    sort(Points+1,Points+n+1);
    int top = 0;
    for(int i=1; i<=n; i++) {
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) {
            if(area(Points[stk[top-1]],Points[stk[top]],Points[i]) < 0) {
                used[stk[top--]] = false;
            } else top--;
        }
        stk[++top] = i;
        used[i] = true;
    }
    used[1] = false;
    for(int i=n; i>=1; i--) {
        if(used[i]) continue;
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) top--;
        stk[++top] = i;
    }
    int num = top-1;
    for(int i=1; i<=num; i++) {
        int x = Points[stk[i]].x, y = Points[stk[i]].y;
        e[i] = e[i+num] = {x,y};
    }
    ll ans = 0;
    for(int i=1; i<num; i++) {
        for(int j=i+1; j<=num; j++) {
            ll x1 = e[i].x,y1 = e[i].y;
            ll x2 = e[j].x,y2 = e[j].y;
            ans = max(ans,get_two_dis({x1,y1},{x2,y2}));
        }
    }
    if(stk[top] == stk[top-1]) ans = get_two_dis(Points[1],Points[n]);
    printf("%lld\n",ans);
}

int main() {
    ll n,r;
    cin >> n;
    for(int i=1; i<=n; i++) {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        Points[i] = {x,y};
    }
    andrew(n);
    return 0;
}



思路枚举凸包上的点i,和i+1组成的一条边,然后三分，别忘了成环要2倍点的数量！
K - Blowing Candles
https://codeforces.com/gym/101635/attachments
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;

struct Point {
    ll x,y;
    Point operator - (Point O) {
        return {x - O.x,y - O.y};
    }
}Points[N],e[N<<1];

bool operator < (Point &a,Point &b) {
    if(a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

double get_length(Point a) {
    return sqrt(a.x * a.x + a.y * a.y);
}

double cross(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

double get_dis(Point p,Point a,Point b) {
    Point v1 = b - a,v2 = p - a;
    return fabs(cross(v1,v2) / get_length(v1));
}

double get_two_dis(Point a,Point b) {
    double dx = a.x - b.x;
    double dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}

int stk[N];
bool used[N];

double area(Point a,Point b,Point c) {
    return cross(b - a,c - a);
}

double ans;

void three_search(int x1,int y1,int x2,int y2,int num,int idx) {
    int l = idx + 2,r = l + num - 3;
    double res = 0;
    while(l <= r) {
        int lmid = l + (r - l) / 3,rmid = r - (r - l) / 3;
        double ldis = get_dis(e[lmid],{x1,y1},{x2,y2});
        double rdis = get_dis(e[rmid],{x1,y1},{x2,y2});
        if(rdis > ldis) l = lmid+1,res = rdis;
        else r = rmid-1,res = ldis;
    }
    ans = min(ans,res);
}

void andrew(ll &n) {
    sort(Points+1,Points+n+1);
    int top = 0;
    for(int i=1; i<=n; i++) {
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) {
            if(area(Points[stk[top-1]],Points[stk[top]],Points[i]) < 0) {
                used[stk[top--]] = false;
            } else top--;
        }
        stk[++top] = i;
        used[i] = true;
    }
    used[1] = false;
    for(int i=n; i>=1; i--) {
        if(used[i]) continue;
        while(top >= 2 && area(Points[stk[top-1]],Points[stk[top]],Points[i]) <= 0) top--;
        stk[++top] = i;
    }

    //所有的边
    /*
    for(int i=1; i<top; i++) {
        printf("%d %d %d %d\n",Points[stk[i]].x,Points[stk[i]].y,Points[stk[i+1]].x,Points[stk[i+1]].y);
    }*/
    //cout<<"top = "<<top<<endl;
    int num = top-1;
    for(int i=1; i<=num; i++) {
        int x = Points[stk[i]].x, y = Points[stk[i]].y;
        e[i] = e[i+num] = {x,y};
    }
    for(int i=1; i<=num; i++) {
        int x1 = e[i].x, y1 = e[i].y;
        int x2 = e[i+1].x, y2 = e[i+1].y;
        three_search(x1,y1,x2,y2,num,i);
    }
}

int main() {
    ans = 1e18;
    ll n,r;
    cin >> n >> r;
    for(int i=1; i<=n; i++) {
        ll x,y;
        scanf("%lld%lld",&x,&y);
        Points[i] = {x,y};
    }
    andrew(n);
    printf("%.15f\n",ans);
    return 0;
}



//极角排序
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int N = 2e5+9;
typedef long long ll;
struct Point {
    ll x,y;
    int id;
}Points[N];

bool cmp(Point a,Point b) {
    if(atan2(a.y,a.x) != atan2(b.y,b.x)) return atan2(a.y,a.x) < atan2(b.y,b.x);
    return a.x < b.x;
}

ll dot(Point a,Point b) {
    return a.x * b.x + a.y * b.y;
}

ll det(Point a,Point b) {
    return a.x * b.y - a.y * b.x;
}

int main() {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        Points[i] = {x,y,i};
    }
    sort(Points+1,Points+n+1,cmp);
    int ans1 = 1,ans2 = n; //注意别忘了1,n之间的角度！
    for(int i=1; i<n; i++) {
        Point v1 = {dot(Points[i],Points[i+1]),abs(det(Points[i],Points[i+1]))};
        Point v2 = {dot(Points[ans1],Points[ans2]),abs(det(Points[ans1],Points[ans2]))}; //这里为啥有绝对值！
        if(det(v1,v2) > 0) ans1 = i,ans2 = i+1;
		//这里把向量点i和ans1旋转到x轴 坐标为 a.x * cos / |b| , a.y * sin / |b|;
		//之后若叉积为正则表示v2 在 v1 上方所以 i 和 i+1 的夹角更小！
    }
    cout<<Points[ans1].id<<" "<<Points[ans2].id<<"\n";
    return 0;
}


#include<bits/stdc++.h>
using namespace std;
const double eps = 1e-8;

struct Point {
    int x,y;
};

int sign(double x) {// 符号函数
    if (fabs(x) < eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) { // 比较函数
    if (fabs(x - y) < eps) return 0;
    if (x < y) return -1;
    return 1;
}

double dot(Point a, Point b) {
    return a.x * b.x + a.y * b.y;
}

double cross(Point a, Point b) { //det;
    return a.x * b.y - b.x * a.y;
}

double get_length(Point a) {
    return sqrt(dot(a, a));
}

double get_angle(Point a, Point b) {
    return acos(dot(a, b) / get_length(a) / get_length(b));
}

double area(Point a, Point b, Point c) {
    return cross(b - a, c - a);
}

Point rotate(Point a, double angle) {
    return Point(a.x * cos(angle) + a.y * sin(angle), -a.x * sin(angle) + a.y * cos(angle)); //顺时针旋转，逆时针angle取相反数代入公式!
}
//x'=xcosθ-ysinθ
//y'=xsinθ+ycosθ //逆时针旋转！
/*
精度损失太大！
平面任意一点 x,y 绕 x0,y0 旋转 a 角度公式！
x0= (x - rx0)*cos(a) - (y - ry0)*sin(a) + rx0 ;
y0= (x -rx0)*sin(a) +(y - ry0)*cos(a) + ry0;
*/
int main() {

    return 0;
}

//利用atan2（）函数按极角从小到大排序。
//第三象限开始！

#include<bits/stdc++.h>
using namespace std;

typedef pair<double,double> PDD;
typedef pair<int,int> PII;

#define x first
#define y second

vector<PDD> Points;

bool cmp(PDD a,PDD b)
{
    if(atan2(a.y,a.x)!=atan2(b.y,b.x))
        return atan2(a.y,a.x)<atan2(b.y,b.x);
    else return a.x<b.x;
}

int main() {
    int n;
    cin >> n;
    for(int i=1; i<=n; i++) {
        double x,y;
        cin >> x >> y;
        Points.push_back({x,y});
    }
    sort(Points.begin(),Points.end(),cmp);
    for(auto v : Points) {
        cout<<v.first<<" "<<v.second<<endl;
    }
    return 0;
}


有向图tarjan
void tarjan(int u)
{
    low[u] = dfn[u] = ++timestamp;
    stk[++top] = u,in_stk[u] = true;
    for(int i=head[u]; ~i; i=e[i].next) 
    {
        int v = e[i].to;
        if(!dfn[v]) 
        {
            tarjan(v);
            low[u] = min(low[u],low[v]);
        }
        else if(in_stk[v]) 
        {
            low[u] = min(low[u],dfn[v]);
        }
    }
    if(low[u] == dfn[u]) 
    {
        scc_cnt++;
        int y;
        do  
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt]++;
        }
        while(y != u);
    }
}

for(int i=1; i<=n; i++) 
{
    if(!dfn[i]) tarjan(i);
}


有向图Dijkstra()邻接矩阵！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

typedef long long ll;
const int N = 509;

int g[N][N],dist[N];
int n,m;
bool st[N];

void Dijkstra() {
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    for(int i=1; i<=n; i++) {
        int t = -1;
        for(int j=1; j<=n; j++) {
            if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        st[t] = true;
        for(int j=1; j<=n; j++) {
            dist[j] = min(dist[j],dist[t] + g[t][j]);
        }
    }
    if(dist[n] == 0x3f3f3f3f) puts("-1");
    else cout<<dist[n]<<endl;
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            g[i][j] = (i == j ? 0 : 0x3f3f3f3f);
        }
    }
    while(m--) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[a][b] = min(g[a][b],c);
    }
    Dijkstra();
    return 0;
}

有向图Dijkstra()邻接表！

int head[N],numE,dist[N];
bool st[N];
int n,m;
struct E {
    int next,to,w;
}e[N << 1];

void add(int a,int b,int c) {
    e[numE] = {head[a],b,c};
    head[a] = numE++;
}

void Dijkstra() {
    priority_queue<PII,vector<PII>,greater<PII>> qu;
    memset(dist,0x3f,sizeof dist);
    dist[1] = 0;
    qu.push({0,1});
    while(!qu.empty()) {
        auto t = qu.top();
        qu.pop();
        int ver = t.second;
        if(st[ver]) continue;
        st[ver] = true;
        for(int i=head[ver]; ~i; i=e[i].next) {
            int v = e[i].to;
            if(dist[v] > dist[ver] + e[i].w) {
                dist[v] = dist[ver] + e[i].w;
                qu.push({dist[v],v});
            }
        }
    }
    if(dist[n] == 0x3f3f3f3f) cout<<"-1\n";
    else cout<<dist[n]<<"\n";
}

int main() {
    memset(head,-1,sizeof head);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; i++) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
    }
    Dijkstra();
    return 0;
}

有向图的拓扑序列
const int N = 1e5+9;
int head[N],numE;
int in[N];

struct E {
    int next,to;
}e[N << 1];

void add(int a,int b) {
    e[numE] = {head[a],b};
    head[a] = numE++;
}

void topological_sort(int &n) {
    int hh = 1,tt = 0;
    int qu[N];
    for(int i=1; i<=n; i++) {
        if(!in[i]) qu[++tt] = i;
    }
    while(hh <= tt) {
        int t = qu[hh++];
        for(int i=head[t]; ~i; i=e[i].next) {
            int v = e[i].to;
            in[v]--;
            if(!in[v]) qu[++tt] = v;
        }
    }
    if(tt == n) {
        for(int i=1; i<=tt; i++) printf("%d%s",qu[i],i == tt ? "\n" : " ");
    } else puts("-1");
}


有边数限制的最短路
#include<iostream>
#include<string.h>
using namespace std;
const int M = 2e4+9;
const int N = 509;
int n,m,k;
int dist[N],last[N];
struct Edge 
{
    int a,b,w;
}edge[M];
bool Bellman_ford()
{
    memset(dist,0x3f,sizeof(dist));
    dist[1] = 0;
    for(int i=1; i<=k; i++)
    {
        memcpy(last,dist,sizeof(dist));
        for(int j=1; j<=m; j++)
        {
            auto t = edge[j];
            dist[t.b] = min(dist[t.b],last[t.a] + t.w);
        }
    }
    if(dist[n] > 0x3f3f3f3f/2) return false;
    return true;
}
int main()
{
    cin >> n >> m >> k;
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        edge[i] = {a,b,c};
    }
    if(Bellman_ford()) cout<<dist[n]<<endl;
    else cout<<"impossible"<<endl;
    return 0;
}

SPFA最短路！
void SPFA() {
    queue<int> qu;
    memset(dist,0x3f,sizeof dist);
    qu.push(1);
    dist[1] = 0;
    st[1] = true;
    while(!qu.empty()) {
        int t = qu.front();
        qu.pop();
        st[t] = false;
        for(int i=head[t]; ~i; i=e[i].next) {
            int v = e[i].to;
            if(dist[v] > dist[t] + e[i].w) {
                dist[v] = dist[t] + e[i].w;
                if(!st[v]) {
                    st[v] = true;
                    qu.push(v);
                }
            }
        }
    }
    if(dist[n] >= 0x3f3f3f3f / 2) cout<<"impossible\n"; 
    else cout<<dist[n]<<"\n";
}

判断负环！
bool spfa()
{
    queue<int> qu;
    for(int i=1; i<=n; i++)
    {
        st[i] = true;
        qu.push(i);
    }
    while(!qu.empty())
    {
        int t = qu.front();
        qu.pop();
        st[t] = false;
        for(int i=head[t]; ~i; i=e[i].next)
        {
            int v = e[i].to;
            if(dist[v] > dist[t] + e[i].w)
            {
                dist[v] = dist[t] + e[i].w;
                if(!st[v])
                {
                    cnt[v] = cnt[t] + 1;
                    if(cnt[v] >= n) return true;
                    st[v] = true;
                    qu.push(v);
                }
            }
        }
    }
    return false;
}


 floyd
 memset(g,0x3f,sizeof g);
 cin >> n >> m >> k;
 for(int i=0; i<=n; i++) g[i][i] = 0;
 for(int i=1; i<=m; i++)
 {
     int a,b,c;
     cin >> a >> b >> c;
     g[a][b] = min(g[a][b],c);
 }
 for(int k=1; k<=n; k++)
 {
     for(int i=1; i<=n; i++)
     {
         for(int j=1; j<=n; j++) g[i][j] = min(g[i][j],g[i][k] + g[k][j]);
     }
 }
 while(k--)
 {
     int a,b;
     cin >> a >> b;
     if(g[a][b] >= 0x3f3f3f3f / 2) cout<<"impossible\n";
     else cout<<g[a][b]<<"\n";
 }

prim
#include<bits/stdc++.h>
using namespace std;
const int N = 509;
int n,m;
int g[N][N],dist[N],st[N];
int prim()
{
    memset(dist,0x3f,sizeof dist);
    int res = 0;
    for(int i=1; i<=n; i++)
    {
        int t = -1;
        for(int j=1; j<=n; j++)
        {
            if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;
        }
        if(i != 1 && dist[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i > 1) res += dist[t];
        st[t] = true;
        for(int j=1; j<=n; j++) dist[j] = min(dist[j],g[t][j]);
    }
    return res;
}
int main()
{
    memset(g,0x3f,sizeof(g));
    cin >> n >> m;
    for(int i=1; i<=m; i++)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        g[b][a] = g[a][b] = min(g[a][b],c);
    }
    int t = prim();
    if(t == 0x3f3f3f3f) puts("impossible");
    else cout<<t<<endl;
    return 0;
}

染色法判定二分图！
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5+9;
int idx,e[N],ne[N];
int h[N],color[N];
int n,m;
bool ok;
void add(int a,int b)
{
    e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}
bool dfs(int u,int num)
{
    color[u] = num;
    for(int i=h[u]; ~i; i=ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(dfs(j,3 - num) == false) return false;
        }
        else
        {
            if(color[j] == num) return false;
        }
    }
    return true;
}

int main()
{
    ok = true;
    memset(h, -1,sizeof h);
    cin >> n>> m;
    for(int i=1; i<=m; i++)
    {
        int a,b;
        cin >> a >> b;
        add(a,b);
        add(b,a);
    }
    for(int i=1; i<=n; i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                ok = false;
                break;
            }
        }
    }
    if(ok) puts("Yes");
    else puts("No");
    return 0;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
11-29 22:16
点赞 评论 收藏
分享
11-20 10:43
门头沟学院 嵌入式软件开发
中石油的压迫感太强了
不愧是全球top的央企
整顿职场的柯基很威猛：这种不可怕，最可怕的是夹在一帮名校里的二本选手，人家才是最稳的。
点赞 评论 收藏
分享
10-09 00:50
已编辑
长江大学 算法工程师
全村唯一的指望了，怎么就偏偏是你。
成也华子，败也华子，如今竟然只能指望着华子了，害。投的是计算产品线，因为研究方向是ai-infra，只有这个最对口了。因为祖上传下来的xcpc金所以免机考+一次面试，实际在南研所只面了两轮。---------分割线---------但是我不想去，因为逆反。华子是家里唯一承认的私企。去这里等价于又一次屈服于他们。（想啥呢，人家还没给你发offer呢）
不期而遇的夏天：1.同学你面试评价不错，概率很大，请耐心等待；2.你的排名比较靠前，不要担心，耐心等待；3.问题不大，正在审批，不要着急签其他公司，等等我们！4.预计9月中下旬，安心过节；5.下周会有结果，请耐心等待下；6.可能国庆节前后，一有结果我马上通知你；7.预计10月中旬，再坚持一下；8.正在走流程，就这两天了；9.同学，结果我也不知道，你如果查到了也告诉我一声；10.同学你出线不明朗，建议签其他公司保底！11.同学你找了哪些公司，我也在找工作。
点赞 评论 收藏
分享
11-27 10:51
东南大学 单片机
听学长的没错
拿到了2个offer，分别是携程的后端和阿里云的管培生，本来比较犹豫，跟就业办的老师聊了之后豁然开朗，他说阿里云管培生是非常难得的校招生培养项目，算是技术复合型人才的黄埔军校是非常适合技术复合型人才的职业发展第一站，不仅可以带薪培训1年，系统学习云计算产品与技术知识，还能接触到阿里云顶级的行业资源，接触业务和商业知识，挺适合我这种对技术商业化更感兴趣的人，而且有同专业的学长也在这个项目里，说不定还能有个饭搭子跟着前辈学，经验成长肯定快！就不纠结了，直接接了这个阿里云管培生offer，希望未来发展顺利！早日成为大佬哈哈
Java抽象带篮子：要我就选携程了，技术人一开始就走技术岗好一些
点赞 评论 收藏
分享
评论
点赞
收藏
分享

全站热榜

正在热议
# 拼多多求职进展汇总 #
240629次浏览 2051人参与
# 实习，投递多份简历没人回复怎么办 #
2447539次浏览 34795人参与
# 北方华创开奖 #
67971次浏览 558人参与
# 25届秋招总结 #
425111次浏览 4294人参与
# 虾皮求职进展汇总 #
100470次浏览 810人参与
# 地方国企笔面经互助 #
7368次浏览 18人参与
# 阿里云管培生offer #
65361次浏览 1766人参与
# ai智能作图 #
35422次浏览 434人参与
# 中兴求职进展汇总 #
471041次浏览 2453人参与
# 我在牛爱网找对象 #
75230次浏览 556人参与
# 双非有机会进大厂吗 #
106171次浏览 1333人参与
# 实习想申请秋招offer，能不能argue薪资 #
37966次浏览 313人参与
# 机械求职避坑tips #
24207次浏览 252人参与
# 发工资后，你做的第一件事是什么 #
10579次浏览 52人参与
# 25届机械人为了秋招做了哪些准备？ #
26799次浏览 366人参与
# 投格力的你，拿到offer了吗？ #
47873次浏览 337人参与
# 我的实习求职记录 #
6144647次浏览 84084人参与
# 投递实习岗位前的准备 #
1193664次浏览 18510人参与
# 机械人怎么评价今年的华为 #
158453次浏览 1354人参与
# 在职场上，你最讨厌什么样的同事 #
6476次浏览 96人参与
# 实习与准备秋招该如何平衡 #
725967次浏览 8568人参与
# 华为工作体验 #
112482次浏览 871人参与
牛客网
牛客企业服务