hdu3861 The King’s Problem 强连通缩点+DAG最小路径覆盖

　　对多校赛的题目，我深感无力。题目看不懂，英语是能懂的，题目具体的要求以及需要怎么做没有头绪。样例怎么来的都不明白。好吧，看题解吧。

　　http://www.cnblogs.com/kane0526/archive/2013/07/21/3203992.html

题目大意：

　　把一幅有向图中的点最少可以划分为几个区域。划分的规则是：1、可以互相到达的点必须在同一区域。2、每个城市都必须被划分。3、对于属于同一区域中的任意两点，要么满足u->v,要么满足v->u。

　　第三条规则需要着重解释一下。对于测试数据1->2,1->3，因为2与3之间没有边，所以2与3必须被划为2个区域。所以答案是2。

做法：

　　建图求强连通（Tarjan算法），然后对得到的DAG，重新建图。遍历每条边，不属于同一连通分支的点就连一条边。正向图和反向图都可以。

　　最后答案就是SCC - ans。SCC 是连通分支数，ans是最大匹配数。因为这里求的最小路径覆盖。

　　最小路径覆盖 = 顶点数 - 最大匹配数

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<vector>

 #include<queue>

 #include<algorithm>

 using namespace std;

 const int N =, M=,INF=0x3f3f3f3f;;

 struct node

 {

     int to, next;

 }edge[M];

 int head[N], low[N], dfn[N], sta[N], belg[N], num[N];

 bool vis[N];

 int scc,index,top, tot;

 void tarbfs(int u)

 {

     int i,j,k,v;

     low[u]=dfn[u]=++index;

     sta[top++]=u;

     vis[u]=;

     for(i=head[u];i!=-;i=edge[i].next)

     {

         v=edge[i].to;

         if(!dfn[v])

         {

             tarbfs(v);

             if(low[u]>low[v]) low[u]=low[v];

         }

         else if(vis[v]&&low[u]>dfn[v]) low[u]=dfn[v];

     }

     if(dfn[u]==low[u])

     {

         scc++;

         do

         {

             v=sta[--top];

             vis[v]=;

             belg[v]=scc;

             num[scc]++;

         }

         while(v!=u) ;

     }

 }

 void Tarjan(int n)

 {

     memset(vis,,sizeof(vis));

     memset(dfn,,sizeof(dfn));

     memset(num,,sizeof(num));

     memset(low,,sizeof(low));

     index=scc=top=;

     for(int i=;i<=n;i++)

         if(!dfn[i]) tarbfs(i);

 }

 void init()

 {

     tot=;

     memset(head,-,sizeof(head));

 }

 void addedge(int i,int j)

 {

     edge[tot].to=j; edge[tot].next=head[i];head[i]=tot++;

 }

 int cx[N],cy[N],dx[N],dy[N];

 bool bmask[N];

 int nx,dis,ans;

 vector<int> bmap[N];

 bool searchpath()

 {

     queue<int> q;

     dis=INF;

     memset(dx,-,sizeof(dx));

     memset(dy,-,sizeof(dy));

     for(int i=;i<=nx;i++)

     {

         if(cx[i]==-){ q.push(i); dx[i]=; }

         while(!q.empty())

         {

             int u=q.front(); q.pop();

             if(dx[u]>dis) break;

             for(int i=;i<bmap[u].size();i++)

             {

                 int v=bmap[u][i];

                 if(dy[v]==-)

                 {

                     dy[v]= dx[u] + ;

                     if(cy[v]==-) dis=dy[v];

                     else

                     {

                         dx[cy[v]]= dy[v]+;

                         q.push(cy[v]);

                     }

                 }

             }

         }

     }

     return dis!=INF;

 }

 int findpath(int u)

 {

     for(int i=;i<bmap[u].size();i++)

     {

         int v=bmap[u][i];

         if(!bmask[v]&&dy[v]==dx[u]+)

         {

             bmask[v]=;

             if(cy[v]!=-&&dy[v]==dis) continue;

             if(cy[v]==-||findpath(cy[v]))

             {

                 cy[v]=u; cx[u]=v;

                 return ;

             }

         }

     }

     return ;

 }

 void maxmatch()

 {

     ans=;

     memset(cx,-,sizeof(cx));

     memset(cy,-,sizeof(cy));

     while(searchpath())

     {

         memset(bmask,,sizeof(bmask));

         for(int i=;i<=nx;i++)

             if(cx[i]==-) ans+=findpath(i);

     }

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     int cas,i,j,k,n,m;

     scanf("%d",&cas);

     while(cas--)

     {

         scanf("%d%d",&n,&m);

         init();

         while(m--)

         {

             scanf("%d%d",&i,&j);

             addedge(i,j);

         }

         Tarjan(n);

         for(i=;i<=n;i++) bmap[i].clear();

         for(i=;i<=n;i++)

         {

             for(k=head[i];k!=-;k=edge[k].next)

             {

                 j=edge[k].to;

                 if(belg[i]!=belg[j]) bmap[belg[j]].push_back(belg[i]);

             }

         }

         nx=scc;

         maxmatch();

         printf("%d\n",scc-ans);

     }

     return ;

 }

巴特西

hdu3861 The King’s Problem 强连通缩点+DAG最小路径覆盖

最新文章

热门文章