XtestW's Blog

Tarjan算法

发表于 2013-07-28 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

两篇讲的比较好的文章: https://www.byvoid.com/blog/scc-tarjan/ https://www.byvoid.com/blog/biconnect/ 对于有向图和无向图，处理的大体方法一样的，不过概念不同 /*****************************************************************************/ tarjan在处理无向图的时候，遇到两点之间的有多条边的时候处理方法，和如何缩点，缩边代码：


void tarjan(int s,int pre)
{
    low[s]=dfn[s]=cnt++;
    vis[s]=true;
    int f=0;
    stk.push(s);
    //stk[stkCnt++]=s;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int u=e[i].to;
        if (u==pre){f++; continue;}
        if (!dfn[u]){
            tarjan(u,s);
            low[s]=min(low[s],low[u]);
        }
        else if(vis[u])
            low[s]=min(low[s],dfn[u]);
    }
    if (f>=2) return;//这里用f处理了点与点之间如果遇到多条边的情况
    if (low[s]==dfn[s]){
            while (true)
            {
                //int t=stk[--stkCnt];//stk.pop();
                int t=stk.top();stk.pop();
                flag[t]=xx;
                vis[t]=false;
                if (t==s)
                {
                    break;
                }
            }
            xx++;
    }
}
vector *nMp;//[200010];
void build(int n)
{
   for (int i=0;i<n;i++)
   {//遍历所有的边，判断边的两边是不是在一个集合中的，不是就是割边
       int s,t;
       s=flag[e[i*2].from];
       t=flag[e[i*2].to];
       if (s!=t)
       {
           nMp[s].push_back(t);
           nMp[t].push_back(s);
       }
   }
}

2013多校的第二场B题（hdu 4612） ac代码：

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <cstring>
#include <string>
#include <map>
using namespace std;
int n,m;
vector mp[200010];
struct edge
{
    int from;
    int to;
    int next;
};
edge e[2000020];
int head[200020];
stack stk;
//int stk[200010];
int stkCnt=0;
int flag[200010];
int xx;
int low[200010];
int dfn[200010];
bool vis[200010];
int cnt=0;
void tarjan(int s,int pre)
{
    low[s]=dfn[s]=cnt++;
    vis[s]=true;
    int f=0;
    stk.push(s);
    //stk[stkCnt++]=s;
    for (int i=head[s];i!=-1;i=e[i].next)
    {
        int u=e[i].to;
        if (u==pre){f++; continue;}
        if (!dfn[u]){
            tarjan(u,s);
            low[s]=min(low[s],low[u]);
        }
        else if(vis[u])
            low[s]=min(low[s],dfn[u]);
    }
    if (f>=2) return;
    if (low[s]==dfn[s]){
            while (true)
            {
                //int t=stk[--stkCnt];//stk.pop();
                int t=stk.top();stk.pop();
                flag[t]=xx;
                vis[t]=false;
                if (t==s)
                {
                    break;
                }
            }
            xx++;
    }
}
vector *nMp;//[200010];
void build(int n)
{
  /\*  for (int i=1;i<=n;i++)
   {
       for (int j=head[i];j!=-1;j=e[j].next)
       {
           if (flag[e[j].to]!=flag[i])
           {
               nMp[flag[i]].push_back(flag[e[j].to]);
               nMp[flag[e[j].to]].push_back(flag[i]);
           }
       }
   }*/
   for (int i=0;i<n;i++)
   {
       int s,t;
       s=flag[e[i*2].from];
       t=flag[e[i*2].to];
       if (s!=t)
       {
           nMp[s].push_back(t);
           nMp[t].push_back(s);
       }
   }
}

int ans,root;
void dfs(int now,int pre,int cnt)
{
    if (ans<=cnt)
    {
        ans=cnt;
        root=now;
    }
    for (int i=0;i<nMp[now].size();i++)
    {
        if (nMp[now][i]==pre) continue;
        dfs(nMp[now][i],now,cnt+1);
    }
}

int main()
{
//  int size = 256 << 20; // 256MB
//  char \*p = (char\*)malloc(size) + size;
//  \_\_asm\_\_("movl %0, %%esp\\n" :: "r"(p) );

while (scanf("%d%d",&n,&m)!=EOF)
{
    xx=0;
    memset(flag,-1,sizeof(flag));
    memset(low,0,sizeof(low));
    memset(dfn,0,sizeof(dfn));
    memset(vis,false,sizeof(vis));
   // memset(stk,0,sizeof(stk));
    memset(head,-1,sizeof(head));
    stkCnt=0;
    for (int i=0;i<n+5;i++) mp[i].clear();
    if (m+n==0) break;
    for (int i=0;i<2*m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        e[i].to=b;
        e[i].from=a;
        e[i].next=head[a];
        head[a]=i;
        i++;
        e[i].to=a;
        e[i].from=b;
        e[i].next=head[b];
        head[b]=i;
    }
    tarjan(1,1);
    nMp=new vector[xx+10];
    build(m);
    ans=0;
    root=0;
    dfs(0,0,0);
    dfs(root,root,0);
    printf("%d\\n",xx-1-ans);
   // delete mp;
    delete nMp;
}
    return 0;
}

关于大数据的C(M,N)

发表于 2013-05-01 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

cf181 div 2的C题http://codeforces.com/contest/300/problem/C

long long cal(long long s)//s^(MOD-2)
{
     long long ans=1;
     long long n=MOD-2;
     while (n!=0)
     {
         if (n&1) ans=ans*s%MOD;
         s=s*s;
         n=n>>1;
     }
     return ans;
}

long long C(int m,int n)//f[x]=x! 求的是C(m,n)
{
     return f[m]*cal(f[n]*f[m-n]%MOD)%MOD;
}

//CF181D2C

#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MOD 1000000007
using namespace std;

int a,b,n;
long long f[1000001]={0};

long long power(long long s)
{
    long long n=MOD-2;
    long long ans=1;
    while (n!=0)
    {
        if (n&1) ans=(ans*s)%MOD;
        s=(s*s)%MOD;
        n=n>>1;
    }
    return ans%MOD;
}



long long C(int n,int i)
{
    return f[n]*power(f[n-i]*f[i]%MOD);
}

bool check(int s)
{
    while (s!=0)
    {
        int t=s%10;
        if (t!=a && t!=b) return false;
        s=s/10;
    }
    return true;
}

int main()
{
    scanf("%d%d%d",&a,&b,&n);
    f[0]=1;
    for (int i=1;i<n+1;i++){
      f[i]=(i*f[i-1])%MOD;
    }
    long long ans=0;
    for (long long i=0;i<=n;i++)
    {
        if (check(i*a+(n-i)*b)){ans=(ans+C(n,i))%MOD;}
    }
    printf("%d",ans);
    return 0;
}

kruskal 算法

发表于 2013-04-29 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

kruskal算法的主要思想就是从当前路径中选择一个不能构成环的最小边加入

for (int i=1;i<n;i++)
{
int mi=1000000,k;
for (int j=0;j<m;j++)
{
if ((v[e[j].x] + v[e[j].y]==1 || i==1 ) && e[j].d<mi){ mi=e[j].d; k=j; } } result.push_back(k); v[e[k].x]=1; v[e[k].y]=1; if (mi>ma) ma=mi;
}

因为此算法本质上是一个贪心策略，可以通过并查集进行优化，现将其从小到大排序

int kruskal()//返回最小生成树的和
{
int ans=0;
qsort(e,e+n,cmp);//cmp是将其按d值从小到大排序
for (int i=0;i<m;i++)//m is the number of edges
{
if (find(e[i].x)!=find(e[i].y)) {//判断边的两个端点是否在一个集合
result.push_back(i);
ans+=e[i].d;
}
}
return ans;
}

poj 1861

#include
#include
#include
#include
using namespace std;
struct P{
int x,y,d;
};
P e[15100];
vector result;
int ma=-1;
int v[1002]={0};
int main()
{
int n,m;
scanf(“%d%d”,&n,&m);
for (int i=0;i<m;i++)
scanf(“%d%d%d”,&e[i].x,&e[i].y,&e[i].d);
for (int i=1;i<n;i++)
{
int mi=1000000,k;
for (int j=0;j<m;j++)
{
if ((v[e[j].x] + v[e[j].y]==1 || i==1 ) && e[j].d<mi){ mi=e[j].d; k=j; } } result.push_back(k); v[e[k].x]=1; v[e[k].y]=1; if (mi>ma) ma=mi;
}
cout<<ma<<endl;
cout<<result.size()<<endl;
for (int i=0;i<result.size();i++)
{
cout<<e[result[i]].x<< “ “<<e[result[i]].y<<endl;
}
return 0;
}

POJ 1422

发表于 2013-04-28 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

题意不追溯，关于匈牙利算法看：http://my.oschina.net/xuwei8091/blog/126320。最小路径覆盖等于N-最大匹配

#include #include #include using namespace std;
int T;
int n,m;
int map[200][200];
int vis[200];
int result[200];
bool find(int s)
{
for (int i=1;i<=n;i++)
{
if (map[s][i] && !vis[i])
{
vis[i]=1;
if (result[i]==0 || find(result[i]))
{
result[i]=s;
return true;
}
}
}
return false;
}
int main()
{
scanf(“%d”,&T);
while (T–){
memset(map,0,sizeof(map));
memset(result,0,sizeof(result));
scanf(“%d%d”,&n,&m);
for (int i=0;i

匈牙利二分匹配

发表于 2013-04-28 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

关于算法的说明，可以参看这个大牛的讲解，很详细： http://imlazy.ycool.com/post.1603708.html 直接上代码

bool find(int s)
{
    for (int i=1;i<=n;i++)//从1到n编号
    {
         if (map[s][i] && !visit[i])
        {
            visit[i]=1;
            if (pre[i]==0 || find(pre[i]))
             {
                 pre[i]=s;
                 return true;      
             }
    }
    return false;
}

int hungary()//返回最大匹配数
{
     int ans=0;
     for (int i=1;i<=n;i++)
     {
        memset(visit,0,sizeof(visit));
        if (find(i)) ans++;
     }
     return ans;
}

好吧，具体的代码就应该是这样了，但是二分图是无向图吧。。。有向图，怎么破…

POJ 1061

发表于 2013-04-28 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

题意就不赘诉了，青蛙约会。是一个关于欧几里得扩展的定理的题目

int gcd(int a,int b)//欧几里得求最大公约数
{
if (b==0) return a;
return gcd(b,a%b);
}

int exgcd(int a,int b,int &x,int &y)//欧几里得扩展求ax+by=gcd(a,b)的一组解
{
if (b==0) {x=1;y=0;return a;}
int r=exgcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}

针对本题，需要注意的是， 1.数据比较大，需要用long long 2.因为是时间，所以x不能是负数，如果出现负数怎么办呢？ a*x1+b*y1=d(d=gcd(a,b)),那个转换成 a*(x1+b*n）+b*（y1-a*n)=d 最终x=(x1%b+b)%b;或者(x1+(abs([x1/b])+1)*b)%b; AC代码：

#include #include #include #include #include using namespace std;

int gcd(int a,int b)
{
if (b==0) return a;
return gcd(b,a%b);
}
long long exgcd(long long a,long long b,long long &x,long long &y)
{
if (b==0){ x=1;y=0;return a;}
long long r=exgcd(b,a%b,x,y);
long long t=x;
x=y;
y=t-(a/b)*y;
return r;
}
int main()
{
long long x,y,m,n,L;
cin>>x>>y>>m>>n>>L;
long long s=gcd(n-m,L);
if ((x-y)%s!=0){
cout<<”Impossible”<

并查集

发表于 2013-04-27 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

好吧，前两天做了一场CF，遇到一道并查集的题目，感觉并查集还需学习啊，记录一下具体的算法如下

有father数组，全部初始化为本身
添加一个关系进来的时候，s–t，找到s的祖先a,t的祖先b，将a的father设为b
通过查找祖先，来确定是否在一个集合内

void init(int n){//初始化，节点编号1-n
    for (int i=1;i<=n;i++) father[i]=i;
}

int find(int x)//查找祖先节点
{
	while (father[x]!=x) x=father[x];
	return x;
}

void add(int s,int t)//增加一个关系，改变集合
{
  int a=find(s);
  int b=find(t);
  father[a]=b;
}



bool judge(int s,int t)//判断是不是一个集合
{
    return find(s)==find(t);
}

POJ 1015

发表于 2013-04-25 更新于 2025-01-01 分类于 ACMICPC 阅读次数：

原题的题意是给n个人，每个人对于控辩两方都有一个值，现在选择m个人，使得控辩两方的值的差的和最小，如果有相同的最小值，那么就选择最大的一个。本题的关键是模型的构建，对于每个人都有两种选择，一个是选择，一个是不选择，对于相同的差值，维护一个最大的和值，换言之，就是假设差值一定，从n个人选择m个人使得和最大.可以转换为背包问题。状态转移的方程为f[i][j][k+p[i]]=max{f[i-1][j][k+p[i]],f[i-1][j-1][k]+v[i]},表示前i个人中选择j个人差的和为k的最大的和的和（p[i]是第i个人的控辩双方的值差，v[i]是第i个人的控辩双方的值和）.本题的另外一个难点在于路径的记录，我们知道，动态规划的一个本质就是状态转移，也就是在当前状态记录是由哪个值推倒过来的，就可以逆序退出上个状态的值。同时通过对路径的遍历，从而可以判断当前的第i个人是否被选择过，从而达到了降维的作用。

阅读全文 »