A simple Gaussian elimination problem.

hdu4975:http://acm.hdu.edu.cn/showproblem.php?pid=4975

题意：给你一个n*m的矩阵，矩阵中的元素都是0--9，现在给你这个矩阵的每一行和每一列的和，问你这个矩阵是否存在，唯一，或者不唯一。

题解：这一题就是用传说中的网络流破解。首先建图就是把每一行和每一列看成一个点，行和源点建立一条边，容量为这一行的和，列和汇点建边，容量是这一列的和，然后每一行和每一列建立一边，容量是9.然后跑网络流，如果流量和总和相等，说明有解，然后用判断是否唯一，题解中就是说要判断是否存在环，这里用到了类似tarjan的方法判断是否有环。

 #include<iostream>

 #include<cstring>

 #include<algorithm>

 #include<cstdio>

 #include<queue>

 #define INF 100000000

 using namespace std;

 const int N=;

 const int M=;

 struct Node{

    int v;

    int f;

    int next;

 }edge[M];

 int n,m,u,v,cnt,sx,ex;

 int head[N],pre[N];

 bool vis[N],no[N];

 int st[N],top;//根据题目要求申请

 void init(){

     cnt=;

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

     memset(vis,,sizeof(vis));

     memset(no,,sizeof(no));

 }

 void add(int u,int v,int w){

     edge[cnt].v=v;

     edge[cnt].f=w;

     edge[cnt].next=head[u];

     head[u]=cnt++;

     edge[cnt].f=;

     edge[cnt].v=u;

     edge[cnt].next=head[v];

     head[v]=cnt++;

 }

 bool BFS(){

   memset(pre,,sizeof(pre));

   pre[sx]=;

   queue<int>Q;

   Q.push(sx);

  while(!Q.empty()){

      int d=Q.front();

      Q.pop();

      for(int i=head[d];i!=-;i=edge[i].next    ){

         if(edge[i].f&&!pre[edge[i].v]){

             pre[edge[i].v]=pre[d]+;

             Q.push(edge[i].v);

         }

      }

   }

  return pre[ex]>;

 }

 int dinic(int flow,int ps){

     int f=flow;

      if(ps==ex)return f;

      for(int i=head[ps];i!=-;i=edge[i].next){

         if(edge[i].f&&pre[edge[i].v]==pre[ps]+){

             int a=edge[i].f;

             int t=dinic(min(a,flow),edge[i].v);

               edge[i].f-=t;

               edge[i^].f+=t;

             flow-=t;

              if(flow<=)break;

         }

      }

       if(f-flow<=)pre[ps]=-;

       return f-flow;

 }

 int solve(){

     int sum=;

     while(BFS())

         sum+=dinic(INF,sx);

     return sum;

 }

 bool dfs(int u,int pre,bool flag){

     vis[u] = ;

     st[top++] = u;

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

         int v = edge[i].v;

         if(edge[i].f<=)continue;

         if(v == pre)continue;

         if(!vis[v]){

             if(dfs(v,u,edge[i^].f >))return true;

         }

         else if(!no[v])return true;

     }

     if(!flag){

         while(){

             int v = st[--top];

             no[v] = true;

             if(v == u)break;

         }

     }

     return false;

 }

 int main(){

    int T,sumc,sumr,ans,temp,tt=;

    scanf("%d",&T);

    while(T--){

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

       init();

       ans=,sumc=sumr=;sx=;ex=n+m+;

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

           scanf("%d",&temp);

           add(sx,i,temp);

           sumr+=temp;

           for(int j=;j<=m;j++)

             add(i,j+n,);

       }

       for(int i=;i<=m;i++){

           scanf("%d",&temp);

           add(i+n,ex,temp);

           sumc+=temp;

       }

       top=;

       if(sumr!=sumc){

           ans=;

       }

       else if(sumr!=solve()){

          ans=;

       }

      else if(dfs(n+m+,n+m+,)){

          ans=;

      }

      if(ans==)

         printf("Case #%d: So naive!\n",tt++);

      else if(ans==)

         printf("Case #%d: So simple!\n",tt++);

      else

         printf("Case #%d: So young!\n",tt++);

    }

 }

巴特西

A simple Gaussian elimination problem.

最新文章

热门文章