最大匹配

FZU 2039 Pets

Posted on

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名。匈牙利算法是基于Hall定理中充分性证明的思想,它是部图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法。

其实说白了 这个算法用途有限 只能求二分图的最大匹配(如果没有任何扩展,毕竟我是鶸……

题目是一个人与狗的故事
这里每个人都想日狗 所以肯定是一对一的啊 但总共有 n个人 m只狗 e个先决条件
这些条件中 第ai个人不喜欢第bi只狗
问最多能让多少人 日到狗

AC Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <cmath>
#include <iostream>
#include <cstdlib>

using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=1100;
int n,m,qnum;
int cus[maxn];
bool vis[maxn],g[maxn][maxn];

void init()
{
    memset(g,true,sizeof g);
    memset(cus,0,sizeof cus);
    int u,v;
    for(int i=0; i<qnum; i++)
    {
        scanf("%d%d",&u,&v);
        g[u][v]=false;
    }
}

bool fin(int a)
{
    for(int i=1; i<=m; i++)
        if(g[a][i]&&!vis[i])
        {
            vis[i]=true;
            if(cus[i]==0||fin(cus[i]))
            {
                cus[i]=a;
                return true;
            }
        }
    return false;
}

int main()
{
    int test;
    scanf("%d",&test);
    for(int t=1; t<=test; t++)
    {
        scanf("%d%d%d",&n,&m,&qnum);
        init();
        int ans=0;
        for(int i=1; i<=n; i++)
        {
            memset(vis,false,sizeof vis);
            if(fin(i)) ans++;
        }
        printf("Case %d: %d\n",t,ans);
    }
    return 0;
}
DFS

CodeForces 14D Two Paths

Posted on

一看到这道题我就是大写的懵逼
因为上半年去华科还是地大打邀请赛的时候做过类似的题目,当初是写不来的 结果现在……………………还是写不来………………造孽啊

题意:
给你一个无向不成环的图 让你找出两条不相交的树链 使其乘积最大

思路 :
枚举每一条道路 并使其暂时断裂 再从这条道路的两端开始搜索 寻找最长的树链即可
说实话 搜索的题目虽然说做的还凑合 但是这种给你一个连通方式 并以此形成无向图 再加以搜索的题目我还是第一次做
我先想得是用二维矩阵保存路径 以G[u][v] 表示从 u到v是连通的 再用vector省点空间
之后我较为习惯的用了BFS 然后就进入了无限懵逼崩溃懵逼崩溃的状态 说到底用矩阵保存如果不用上结构体的话 很难记录链长
无奈还是写了DFS

AC Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>

using namespace std;
const int maxn=220;
bool vis[maxn];
vector<int> G[maxn];
int ans;

int dfs(int v,int x)
{
    int sum=0;
    int max1=0,max2=0;
    for(int i=0; i<G[v].size(); i++)
    {
        if(G[v][i]!=x)
        {
            sum=max(sum,dfs(G[v][i],v));//sum得到从一个NODE出发的树的直径   循环操作得到最大
                                        //与此同时 ans也在计算着从改点出发的最长树链
            if(ans>max1)
            {
                max2=max1;
                max1=ans;
            }
            else max2=ans>max2?ans:max2;
        }
    }
    sum=max(sum,max1+max2);//最后sum得到从V出发的树的直径
    ans=max1+1;//max1为该node的最长树链  因为递归返回  最大树链长度+1
    return sum;
}

int main()
{
    int n,a,b;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0; i<=n; i++) G[i].clear();
        for(int i=0; i<n-1; i++)
        {
            scanf("%d%d",&a,&b);
            G[a].push_back(b);
            G[b].push_back(a);
        }
        int last_ans=0;
        for(int i=0; i<n; i++)
        {
            int num=G[i].size(),temp;
            for(int j=0; j<num; j++)
            {
                int ans=0;
                temp=dfs(i,G[i][j])*dfs(G[i][j],i);
                last_ans=max(last_ans,temp);
            }
        }
        printf("%d\n",last_ans);
    }
    return 0;
}
单调栈

POJ 3494 Largest Submatrix of All 1’s

Posted on

题意:
给你一个矩阵 全由0,1组成 让你找出其中由1组成的面积最大的矩形
题意非常简单 但让人无从下手
其实如果我们一行一行处理 将矩阵转换到 柱状图 就有想法了
eg

1 0 1 00 0 1 0
0 1 1 1-->0 1 2 1
1 1 0 1-->1 2 0 2
1 0 1 12 0 1 3

再对每一行进行计算连续的最大矩形面积即可

我的方法是直接把 terrible set 的方法拉过来用的 事实证明 效率还好

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath>

using namespace std;

int row,col,ans,tw,temp,top;
int mat[2010][2010];

struct grid
{
    int wid,high;
    grid(int a=0,int b=1):high(a),wid(b){}
}st[2010];

void push(int h)
{
    tw=temp=0;
    while(top>0)
    {
        if(st[top].high>h)
        {
            tw+=st[top].wid;
            if((temp=tw*st[top].high)>ans)
                ans=temp;
            top--;
        }
        else break;
    }
    tw++;
    if((temp=tw*h)>ans) ans=temp;
    if(h)  st[++top]=grid(h,tw);
}

int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        for(int i=1; i<=row; i++)
            for(int j=1; j<=col; j++)
                scanf("%d",&mat[i][j]);
        for(int i=1; i<=col; i++)
            mat[0][i]=0;
        ans=0;
        for(int i=1; i<=row; i++)
        {
            top=0;
            for(int j=1; j<=col; j++)
                if(mat[i][j]) mat[i][j]+=mat[i-1][j];
            for(int j=1; j<=col; j++)
                push(mat[i][j]);
            tw=temp=0;
            while(top>0)
            {
                tw+=st[top].wid;
                if((temp=tw*st[top].high)>ans)
                    ans=temp;
                top--;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}
数状数组

POJ 2299 Ultra-QuickSort

Posted on

去年第一次看到这个马桶塞 是俱乐部介绍归并排序的时候 当初也写了很久 这里就不说了

现在暑假集训 放在树状数组专题 没多久就有了想法

但是以下算法适合应对数据较小的题目 此题不适合 可看可不看

假如以我们一个人的思维求逆序数 我们会计算在它后面的 而且比它小的数字的个数sum 所以我们只要从末尾开始计算 在n位置的前n-1项的sum 就能一个不漏计算出这个位置的逆序数

以样例为例 9 1 0 5 4 先全部初始化为0

1.先计算4 前面全为0 得0

2.计算5 前面有一个4 得1

3.计算0 前面全为0 得0

4.计算1 前面有一个0 得1

5.计算9 前面有0,1 4 5 得4

所有相加的答案 6

结果就是RE了 因为 a[i]的范围是小于等于999,999,999 以上算法必须开这么大的数组 所以RE 不行

没办法 只能去看了题解 看到有指出离散化的思想 卧靠 我完全不懂 又小补了一下离散化 这里就不说了

如果要离散化上述算法 我想是应该将 9 1 0 5 4 想办法 转化成 5 2 1 4 3 但是又要排序又要还原 我就懵逼了

下面是我看的题解思路

开一个结构体记录 下标pos和数值val 以val升序排序 再开个数组 记录排序后的下标

eg

val 9 1 0 5 4-> val 0 1 4 5 9重点来了 大神题解里是按照每个点所影响产生的逆序数 和我上面不一样
pos 1 2 3 4 5 排序离散化-> pos 3 2 5 4 1核心就是 我从头开始放置每一个数 我放第i个数 那么如果是升序的话 我前面理应有i-1个数字
-> reflet 1 2 3 4 5但是因为乱序放置 产生了 i-sum(i) 个逆序数

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
#include <stack>

using namespace std;
int n,maxn;
const int key=500010;

struct node
{
    int val;
    int pos;
};

node nodes[key];
int kao[key],reflect[key];

bool cmp(const node& a, const node& b)
{
    return a.val < b.val;
}
int lowbit(int a)
{
    return a&(-a);
}

void add(int x,int num)
{
    while(x<=n)
    {
        kao[x]+=num;
        x+=lowbit(x);
    }
}

int getsum(int x)
{
    int sum=0;
    while(x)
    {
        sum+=kao[x];
        x-=lowbit(x);
    }
    return sum;
}

int main()
{
    while(scanf("%d",&n),n)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &nodes[i].val);
            nodes[i].pos = i;
        }
        sort(nodes + 1, nodes + n + 1, cmp);
        for (int i = 1; i <= n; i++)
            reflect[nodes[i].pos] = i;
        for (int i = 1; i <= n; i++)
            kao[i] = 0;
        long long ans = 0;
        for (int i = 1; i <= n; i++)
        {
            add(reflect[i],1);
            ans += (i - getsum(reflect[i]));
        }
        printf("%lld\n", ans);
    }
    return 0;
}
BFS

HDU 1728 逃离迷宫

Posted on

真特么蛋疼 一开始我也是把这道题当成常规的 BFS 求最短路径 来写 WA了3发 百思不得其姐 bug怎么找都找不出来 无奈看了一下题解才恍然大悟

这么说吧 题目要求的是 从一个点到另一个点的最小拐弯数

假如说是常规的BFS 从一点到另一点 只能保证路径最短 拐弯数的多少和路径长短是毫无联系的

所以我们每次查找四个方向的时候 直接把一整条直线的grid全都压进队列 因为他们的拐弯数相同 优先级相同

AC Code 感觉时间略长 有待优化 只能助于理解用

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>

using namespace std;
int row,col,limit;
int st_x,st_y,en_x,en_y;
char mat[110][110];
bool vis[110][110];
int dx[]= {-1,0,1,0};
int dy[]= {0,-1,0,1};

struct node
{
    int x,y;
    int step;
    node(int _x,int _y,int _step):x(_x),y(_y),step(_step) {}
};

bool judge(int a,int b)
{
    return a>0&&a<=row&&b>0&&b<=col&&mat[a][b]=='.';
}

void bfs()
{
    queue<node> que;
    que.push(node(st_x,st_y,-2));
    vis[st_x][st_y]=true;
    while(!que.empty())
    {
        node temp=que.front();
        que.pop();
        int x=temp.x,y=temp.y;
        int step=temp.step+1;
        //printf("%d %d %d\n",x,y,step);
        if(x==en_x&&y==en_y&&step<=limit)
        {
            printf("yes\n");
            return ;
        }
        for(int i=0; i<4; i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            while(judge(xx,yy))
            {
                if(!vis[xx][yy])
                {
                    vis[xx][yy]=true;
                    que.push(node(xx,yy,step));
                }
                xx+=dx[i];
                yy+=dy[i];
            }
        }
    }
    printf("no\n");
    return ;
}


int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        scanf("%d%d",&row,&col);
        getchar();
        for(int i=1; i<=row; i++)
        {
            for(int j=1; j<=col; j++)
                scanf("%c",&mat[i][j]);
            getchar();
        }
        scanf("%d%d%d%d%d",&limit,&st_y,&st_x,&en_y,&en_x);
        memset(vis,false,sizeof vis);
        bfs();
    }
    return 0;
}
BFS

HDU 1180 诡异的楼梯

Posted on

集训第二天练习宽搜 写的最郁闷的一题 一个晚上的时间都花在这里了

题目是最普通的宽搜加一个 会变换的楼梯 竖着只能上下走 横着只能左右走

允许停留 跨越楼梯不需要时间

对我来说 题目最大的坑点在于 停留的时候 其他结点都在扩散 如果这时候 直接把结点加入队列 会打散扩散顺序

最后我用了优先队列 还是太辣鸡了啊 唉

AC Code

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>

using namespace std;

struct node
{
    int x,y;
    int step;
    node(int a,int b,int c):x(a),y(b),step(c) {}
    friend bool operator < (const node &a, const node &b)
    {
        return a.step > b.step;
    }
};
int row,col;
int st_x,st_y,en_x,en_y;
char mat[23][23];
bool vis[23][23];
int dx[]= {1,0,-1,0};
int dy[]= {0,-1,0,1};

bool judge(int xx,int yy)
{
    return xx>0&&xx<=row&&yy>0&&yy<=col&&!vis[xx][yy]&&mat[xx][yy]!='*'&&mat[xx][yy]!='-'&&mat[xx][yy]!='|';
}

void bfs()
{
    priority_queue<node> que;
    que.push(node(st_x,st_y,0));
    vis[st_x][st_y]=true;
    bool flag;
    while(!que.empty())
    {
        node temp=que.top();
        que.pop();
        int x=temp.x,y=temp.y;
        int step=temp.step;
        flag=step%2;
        if(x==en_x&&y==en_y)
        {
            printf("%d\n",step);
            return ;
        }
        for(int i=0; i<4; i++)
        {
            int xx=x+dx[i];
            int yy=y+dy[i];
            if(mat[xx][yy]=='|'||mat[xx][yy]=='-')
            {
                if((mat[xx][yy]=='|'&&!flag)||(mat[xx][yy]=='-'&&flag))
                {
                    if(dy[i]==0)
                    {
                        if(judge(xx+dx[i],yy))
                            xx+=dx[i];
                    }
                    else if(judge(xx,yy+dy[i]))
                    {
                        step++;
                        yy+=dy[i];
                    }
                }
                else if((mat[xx][yy]=='-'&&!flag)||(mat[xx][yy]=='|'&&flag))
                {
                    if(dx[i]==0)
                    {
                        if(judge(xx,yy+dy[i]))
                            yy+=dy[i];
                    }
                    else if(judge(xx+dx[i],yy))
                    {
                        step++;
                        xx+=dx[i];
                    }
                }
            }
            if(judge(xx,yy))
            {
                que.push(node(xx,yy,step+1));
                vis[xx][yy]=true;
            }
        }
    }
    return ;
}


int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        getchar();
        for(int i=1; i<=row; i++)
        {
            for(int j=1; j<=col; j++)
            {
                scanf("%c",&mat[i][j]);
                if(mat[i][j]=='S') st_x=i,st_y=j;
                if(mat[i][j]=='T') en_x=i,en_y=j;
            }
            getchar();
        }
        memset(vis,false,sizeof vis);
        bfs();
    }
    return 0;
}
DFS

POJ 1011 sticks

Posted on

题意简单说就是本来几根一样长的棍子 被小明乱切(乱切 没切中也是有可能的) 切成了n根小棍子

要你把n根小棍子恢复原样 可能有多组解

要求输出 每根棍子最短的情况时 棍子长度

据说是极为经典的dfs题

一开始真的不知道怎么搜好(辣鸡无力)闷了1个多小时无奈去看了一下题解 恍然大悟

看完自己敲一A后 细看一下 还是原来那些东西 dfs传参 之前积累的棍长 棍的数量 累加棍的位置

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <stack>

using namespace std;

int stick[70];
bool flag[70];
int len,sum,num,n;//len 棍长   sum所有棍子总长度   num棍数目   n小棍数目

bool dfs(int pre_len,int pre_num,int pos)
{
    if(pre_num==num) return true;
    for(int i=pos;i<n;i++)
    {
        if(flag[i]) continue;
        if(pre_len+stick[i]==len)
        {
            flag[i]=true;
            if(dfs(0,pre_num+1,0)) return true;
            flag[i]=false;//回溯
            return false;
        }
        else if(len>(pre_len+stick[i]))
        {
            flag[i]=true;
            if(dfs(pre_len+stick[i],pre_num,i+1)) return true;
            flag[i]=false;
            if(pre_len==0) return false;//这时 之前一根棍都没有   len>stick[i]
            while(i+1<n&&stick[i]==stick[i+1]) i++;//相邻一样的情况就不用算了
        }
    }
    return false;
}


int main()
{
    while(scanf("%d",&n),n)
    {
        num=sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%d",&stick[i]);
            sum+=stick[i];
        }
        sort(stick,stick+n,greater<int>());
        memset(flag,false,sizeof flag);
        for(len=stick[0];len<=sum;len++)
        {
            if(sum%len) continue;//必须整除
            num=sum/len;//总共棍子的数量
            if(dfs(0,0,0))
            {
                printf("%d\n",len);
                break;
            }
        }
    }
    return 0;
}