头像

想养一只皮卡丘

射洪中学




离线:4天前



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

const int N = 2e5+2;

int n, m;
int ver[N],head[N], Next[N],edge[N],tot;
int color[N];

void add(int x, int y,int z){
    ver[tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot++;
}

bool bfs(int root){
    queue<pair<int, int>> q;
    color[root] = 1;
    q.push({root,1});
    while (q.size()){
        auto t=q.front();
        int  x=t.first;
        int  ver_color=t.second;
        q.pop();
        for(int i=head[x];i;i=Next[i]){
            int y=ver[i];
            if (color[y]==-1){
                color[y]^=ver_color;
                q.push({y,color[y]});
            } 
            else if(color[y]==ver_color) return 0;
        }
    }
    return 1;
}

int main(){
    memset(color,-1, sizeof color);
    int n,m;
    cin >> n >> m;
    while(m--){
        int x, y;
        cin >> x >> y;
        add(x,y,0); add(y,x,0);  
    }
    bool flag = true;
    for(int i = 1; i <= n; i ++) {
        if (color[i] == -1){
            if(!bfs(i)){
                flag = false;
                break;
            }
        }
    }
    if (flag) cout << "Yes";
    else cout << "No";
    return 0;
}



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

const int N=100010;
int head[N],ver[N],Next[N],edge[N],tot;
int v[N];
int match[N];

void add(int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
//从x出发能否找到增广路
int dfs(int x)
{
    for(int i = head[x] ; i != -1 ;i = Next[i])
    {
        int j = ver[i];
        if(!v[j])
        {
            v[j] = true;
            if(!match[j]||dfs(match[j]))
            {
                match[j] = x;
                return true;
            }

        }
    }
   return false;   //return位置别放错了
}

int main(){
    memset(head,-1,sizeof(head));
    int n1,n2,m;cin>>n1>>n2>>m;
    for(int i=1;i<=m;i++){
        int u,v;cin>>u>>v;
        //每次都是从左边点集出发,所以只能由左边指向右边
        add(u,v,0);
    }
    int ans=0;
    for(int i=1;i<=n1;i++){
        memset(v,0,sizeof(v));
        if(dfs(i))  ans++;
    }
    cout<<ans;
    return 0;
}



代码参照蓝皮书

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int head[N*2],ver[N*2],Next[N*2],edge[N*2];
int dfn[N],low[N],n,m,tot,num;
bool bridge[N*2];

void add(int x,int y,int z){
    ver[++tot]=y, edge[tot]=z, Next[tot]=head[x], head[x]=tot;
}

void tarjan(int x,int in_edge){
    dfn[x]=low[x]=++num;
    for(int i=head[x];i;i=Next[i]){
        int y=ver[i];
        if(!dfn[y]){
            tarjan(y,i);
            low[x]=min(low[x],low[y]);

            if(low[y]>dfn[x])
                bridge[i]=bridge[i^1]=true;
        }
        else if(i!=(in_edge^1))
            low[x]=min(low[x],dfn[y]);
    }
}

int main(){
    cin>>n>>m;
    tot=1;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        add(x,y,0);
        add(y,x,0);
    }
    for(int i=1;i<=n;i++)
        if(!dfn[i]) tarjan(i,0);
    for(int i=2;i<tot;i+=2)
        if(bridge[i])
            cout<<ver[i^1]<<" "<<ver[i]<<endl; 
}




附一张模拟移动的图
无标题.png

#include <bits/stdc++.h>

using namespace std;

const int N = 16;

int n;
int q[N], w[5][N];  //w[5][i]记录5步

//估价函数
int f()
{
    int res = 0;
    for (int i = 0; i + 1 < n; i ++ )
        if (q[i + 1] != q[i] + 1)
            res ++ ;
    return (res + 2) / 3;
}
//检查是否还原
bool check()
{
    for (int i = 0; i < n; i ++ )
        if (q[i] != i + 1)
            return false;
    return true;
}

bool dfs(int depth, int max_depth)
{
    if (depth + f() > max_depth) return false;
    if (check()) return true;

    for (int l = 0; l < n; l ++ )
        for (int r = l; r < n; r ++ )
            for (int k = r + 1; k < n; k ++ )
            {
                //把q[i]复制给w[depth][i]这一维
                memcpy(w[depth], q, sizeof q);
                int x, y;
                //模拟移动(把l到r的书移到第k本书后面)
                for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];
                for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];
                if (dfs(depth + 1, max_depth)) return true;
                //搜索失败,还原q[]
                memcpy(q, w[depth], sizeof q);
            }
    return false;
}

int main()
{
    int T;cin>>T;
    while (T -- )
    {
        cin>>n;
        for (int i = 0; i < n; i ++ ) cin>>q[i];

        int depth = 0;
        while (depth < 5 && !dfs(0, depth)) depth ++ ;
        if (depth >= 5) cout<<"5 or more";
        else cout<<depth;
    }

    return 0;
}



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

#define x first
#define y second

typedef pair<int, int> PII;
typedef pair<int, PII> PIII;

const int N = 1010, M = 200010;

int n, m, S, T, K;
int head[N], rhead[N], ver[M], edge[M], Next[M], tot;
int dist[N], cnt[N];
bool v[N];

void add(int head[],int x,int y,int z){
    ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot;
}
//跑反图
void dijkstra()
{
    //优先队列是一个vector,数组的每个格子存的是一个PII,greater是比较大小的函数
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, T});

    memset(dist, 0x3f, sizeof dist);
    dist[T] = 0;

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver1 = t.y;   //取出点
        if (v[ver1]) continue;
        v[ver1] = 1;

        for (int i = rhead[ver1]; i; i = Next[i])
        {
            int j = ver[i];
            if (dist[j] > dist[ver1] + edge[i])
            {
                dist[j] = dist[ver1] + edge[i];
                heap.push({dist[j], j});//入队
            }
        }
    }
}

int astar()
{
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;
    heap.push({dist[S], {0, S}});      //相比上一个优先队列,多存了一个dist[]

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver1 = t.y.y, distance = t.y.x;
        cnt[ver1] ++ ;                 //计数
        if (cnt[T] == K) return distance;

        for (int i = head[ver1]; i; i = Next[i])
        {
            int j = ver[i];
            if (cnt[j] < K)
                heap.push({distance + edge[i] + dist[j], {distance + edge[i], j}});
        }
    }

    return -1;
}

int main()
{
    cin>>n>>m;
    memset(head, -1, sizeof head);
    memset(rhead, -1, sizeof rhead);

    for (int i = 0; i < m; i ++ )
    {
        int a, b, c;
        cin>>a>>b>>c;
        add(head, a, b, c);
        add(rhead, b, a, c);
    }

    cin>>S>>T>>K;
    if (S == T) K++ ;

    dijkstra();
    cout<<astar();
    return 0;
}



附一张关于dx,dy,ix,iy解析的图
(图片来自另一份题解:[https://www.acwing.com/solution/content/21775/])
7416_260b418204-8f4c96e579549999453c9467edbbe41.png

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

typedef pair<int,int> PII;

const int N=510;

int n,m;
char g[N][N];
int d[N][N];
bool v[N][N];

deque<PII> q;
/*STL提供的双端队列
常用操作有:
1 front/back: 队头/队尾元素值
2 push_front: 从队头入队
3 push_back:  从队尾入队
4 pop_front:  从队头出队
5 pop_back:   从队尾出队
6 clear:      清空队列
*/

int bfs()
{
    memset(v,0,sizeof(v));
    memset(d,0x3f,sizeof(d));
    //下标从(0,0)开始
    q.push_front({0, 0});
    d[0][0] = 0;

    int dx[4] = {-1, -1, 1,  1};     //dx[]和dy[]表示可以去其他点的方向
    int dy[4] = {-1,  1, 1, -1};     
    int ix[4] = {-1, -1, 0,  0};     //id[]和iy[]表示需要踩某个方向的格子才能去到相应的点
    int iy[4] = {-1,  0, 0, -1};     
    char cs[] = "\\/\\/";           //cs[]表示当前点走到4个方向的点理想状态下格子形状(边权是0的状态)

    while (q.size())
    {
        auto t = q.front();
        q.pop_front();

        int x = t.first, y = t.second;
        //控制每个点只出队一次
        if (v[x][y]) continue;
        else v[x][y] = 1;

        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];  //(a,b)代表走到的点的坐标
            int j = x + ix[i], k = y + iy[i];  //(j,k)代表格子
            if (a >= 0 && a <= n && b >= 0 && b <= m) //边界判断
            {
                int w = 0;
                if (g[j][k] != cs[i]) w = 1;  //cs[]是理想状态,若不是cs就需要旋转
                if (d[a][b] > d[x][y] + w)
                {
                    d[a][b] = d[x][y] + w;
                    //若拓展某一元素的边权是0,则将该元素插入到队头
                    //若拓展某一元素的边权是1,则将该元素插入到队尾
                    if(w) q.push_back({a, b});
                    else  q.push_front({a, b});
                }
            }
        }
    }

    if(d[n][m]==0x3f3f3f3f) return -1;
    else return d[n][m];
}

int main()
{
    int T;cin>>T;
    while (T--)
    {
        cin>>n>>m;
        for (int i=0; i<n;i++ ) 
            for(int j=0;j<m;j++)
                cin>>g[i][j];

        int t = bfs();

        if(t==-1) puts("NO SOLUTION");
        else cout<<t<<endl;
    }
    return 0;
}



`#include <bits/stdc++.h>
using namespace std;
const int N=10000010;
long long ans,n,w,g[N],s[N];
long long n2;//s[]数组的指针

long long find(int val)//最大可以承受的值
{
    int l=1,r=n2,check=w-val;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if (s[mid]<=check)l=mid;
        else  r=mid-1;
    }
    ans=max(ans,s[l]+val);//当前最大值与全局最大值开始比较
}

int dfs1(int x,long long sum)
{
    if (x==(n/2+2)+1)
    {
        s[++n2]=sum;//新的权值出现,压入数组中
        return true;//返回必不可少,否则RE
    }
    //可以放进去
    if (sum+g[x]<=w)
        dfs1(x+1,sum+g[x]);
    //不放这个进去
    dfs1(x+1,sum);
}

int dfs2(int x,int sum)
{
    if (x==n+1)
    {
        find(sum);//求出当前可以填充的最大值
        return true;
    }
    if(sum+g[x]<=w)//如果可以放进去
        dfs2(x+1,sum+g[x]);  
    //不放这个进去
    dfs2(x+1,sum);
}

int main()
{
    cin>>w>>n;
    for(int i=1; i<=n; i++)
        cin>>g[i];
    sort(g+1,g+1+n);//从大到小排序
    reverse(g+1,g+1+n);

    dfs1(1,0);
    //离散化
    sort(s+1,s+n2+1);
    n2=unique(s+1,s+n2+1)-(s+1);//去掉重复后,多少个数

    dfs2(n/2+3,0);
    cout<<ans<<endl;
    return 0;
}`



#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,ans,x[N];
bool sum[N];     
//当前now深度,deep最大深度,last为上一次的数值,因为要满足数列的单调递增性.
bool dfs(int now,int deep,int last){
    if(x[now]==n) return 1;    //递归边界
    if(now>=deep) return 0;    //深度限制(这里是大于等于,因为当now=k-1时,已经可以枚举出下一个,x数组中的数的个数刚好和k相等了)
    for(int i=now;i>=1;i--)    //从大到小枚举,快速逼近n
        for(int j=i;j>=1;j--){
            if(!sum[x[i]+x[j]]&&x[i]+x[j]>=last)    //必须是大于等于last,因为可能出现两个数值一样的
                {
                x[now+1]=x[i]+x[j];
                sum[x[i]+x[j]]=1;
                //往下搜
                bool banduan=dfs(now+1,deep,x[i]+x[j]);
                if(banduan)
                    return 1;
                //还原现场
                sum[x[i]+x[j]]=0;
                x[now+1]=0;
                }
        }
    return 0;
}

int main()
{
    while(cin>>n&&n)
    {
        //排除n=1,2的特殊情况
        x[1]=1;
        x[2]=2;
        int k=n;

        if(n>=3)
        {
            //k至少从3开始
            k=3;
            for(;k<=10;k++)
            {
                memset(sum,0,sizeof(sum));
                memset(x,0,sizeof(x));
                x[1]=1;x[2]=2;      //前两个是唯一确定的
                bool s=dfs(2,k,3);
                //或者s=dfs(2,k,2)都可以
                if(s)
                    break;
            }
        }
        for(int i=1;i<=k;i++)
            cout<<x[i]<<" ";
        cout<<endl;
    }
    return 0;
}



#include<bits/stdc++.h>
using namespace std;
const int max1=0x3f3f3f3f;
int n,m;
int minv[22], mins[22], ans=max1;
int h[22],r[22], s=0,v=0;//当前表面积为s,体积为v

void dfs(int dep){
    //处理边界
    if(!dep)
    {
    if (v==n) ans=min(ans,s);
    return; 
    }
    //上下边界剪枝
    for(r[dep]=min((int)sqrt(n-v),r[dep+1]-1);r[dep]>=dep;r[dep]--)
        for(h[dep]=min((int)((double)(n-v)/(r[dep]*r[dep])), h[dep+1]-1); h[dep]>=dep;h[dep]--) 
        {
            //可行性剪枝
            if(v+minv[dep-1]>n)    continue;
            //最优化剪枝一
            if(s+mins[dep-1]>=ans) continue;
            //最优化剪枝二(未来最少花费代价)
            if(s+(double)2*(n-v)/r[dep]>ans) continue;

            if (dep == m) s+=r[dep]*r[dep]; //所有层的裸露的部分的面积
            s+=2*r[dep]*h[dep];           //s=2rh
            v+=r[dep]*r[dep]*h[dep];      //v=rrh
            dfs(dep-1);                       //从下往上搜(优化搜索顺序剪枝)

            if(dep == m)  s-=r[dep]*r[dep]; //还原现场
            s-=2*r[dep]*h[dep];
            v-=r[dep]*r[dep]*h[dep];
        }
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i)//剪枝1:预处理最小的体积和表面积
    {
        minv[i]=minv[i-1]+i*i*i;
        mins[i]=mins[i-1]+i*i;
    }
    h[m+1]=r[m+1]=max1;
    dfs(m);     //从下往上搜(优化搜索顺序剪枝)
    if(ans==max1)
        cout<<0;
    else
        cout<<ans;
}



#include<bits/stdc++.h>
using namespace std;
int a[65],v[65];//a[]记录小木棍,v记录访问
int n,len,cnt;  //原始木棍长len,共cnt根
//正在拼第stick根大木棍,当前长度为cab,上一次拼接的!小!木棍为last
bool dfs(int stick,int cab,int last){
    if(stick>cnt) return 1;//边界
    if(cab==len) return dfs(stick+1,0,1); //last记为1就很妙啊,既可以处理第一根小木棍就填满的特殊情况,也不影响后续搜索
    int fail=0;
    for(int i=last;i<=n;i++)
    {
        if(!v[i]&&cab+a[i]<=len&&fail!=a[i])
        {   
            v[i]=1;
            if(dfs(stick,cab+a[i],i+1)) return 1;
            fail=a[i];       //一旦这条路错了,记录失败的a[i]
            v[i]=0;
            if(cab==0||cab+a[i]==len) return 0;
         }
    }
    return 0;
}

int main(){
    while(cin>>n&&n){
        int sum=0,val=0;
        for(int i=1;i<=n;i++)
            {cin>>a[i];sum+=a[i];val=max(val,a[i]);}
        sort(a+1,a+1+n);reverse(a+1,a+1+n);
        for(len=val;len<=sum;len++)
        {
            if(sum%len) continue;
            cnt=sum/len;      //原始木棍长len,共cnt根,下面开始搜索合不合法
            memset(v,0,sizeof(v));//初始化
            if(dfs(1,0,1)) break;
            //或者if(dfs(1,0,0)) break;
        }
        cout<<len<<endl;
    }
}