记录编号	431470	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010]引水入城	最终得分	100
用户昵称	Hzoi_QTY	是否通过	通过
代码语言	C++	运行时间	0.096 s
提交时间	2017-07-31 20:13:05	内存使用	2.10 MiB

#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,a[505][505],tot=0,vis[505],v[505],ans=0,sum,hh[250005];
struct city
{
     int to[5];
} ci[250002];
struct hhh
{
    int l,r,sum;
    hhh()
    {l=1000;}
} tx[505];
int min(int a,int b){return a<b? a:b;}
void Dfs(int x,int root)
{
     hh[x]=1;
     if(x<=m*n&&x>m*(n-1))
      {
         int k=x%m;
         if(k==0)k=m;
         tx[root].l=min(tx[root].l,k);
         tx[root].r=max(tx[root].r,k);
         tx[root].sum++;
         v[k]=1;
      }
     for(int i=1;i<=ci[x].to[0];i++)
     {
          int k=ci[x].to[i];
          if(!hh[k])
          {
              Dfs(k,root);
          }
     }
}
void dfs(int x,int len,int s)
{
    if(len==m){sum=min(sum,s);return;}
    for(int i=x+1;i<=m;i++)
    {
         if(tx[i].l<=len+1&&tx[i].r>len)
            dfs(i,tx[i].r,s+1);
         if(tx[i].l>len+1)break;
    }
}
int cmp(const hhh &a,const hhh &b)
{
    if(a.l==b.l)return a.r>b.r;
    return a.l<b.l;
}
int yjn()
{
   freopen("flow.in","r",stdin);
   freopen("flow.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
         scanf("%d",&a[i][j]);
   tot=0;
   for(int i=1;i<=n;i++)
      for(int j=1;j<=m;j++)
      {
          tot++;
          if(i!=1&&a[i][j]>a[i-1][j])ci[tot].to[0]++,ci[tot].to[ci[tot].to[0]]=tot-m;
          if(i!=n&&a[i][j]>a[i+1][j])ci[tot].to[0]++,ci[tot].to[ci[tot].to[0]]=tot+m;
          if(j!=1&&a[i][j]>a[i][j-1])ci[tot].to[0]++,ci[tot].to[ci[tot].to[0]]=tot-1;
          if(j!=m&&a[i][j]>a[i][j+1])ci[tot].to[0]++,ci[tot].to[ci[tot].to[0]]=tot+1;
      }
   for(int i=1;i<=m;i++)
      if(a[1][i]>=a[1][i-1]&&a[1][i]>=a[1][i+1])
      {
          Dfs(i,i);
          memset(hh,0,sizeof(hh));
      }
  /* for(int i=0;i<m;i++)
       cout<<v[i]<<" ";*/
   for(int i=1;i<=m;i++)
      if(v[i])
        sum++;
   if(sum!=m)
   {printf("0\n%d",m-sum);exit(0);}
   sort(tx+1,tx+m+1,cmp);
   sum=0;
 /*  for(int i=1;i<=m;i++)
   {
       cout<<tx[i].l<<" "<<tx[i].r<<endl;
   }*/
   int l=1,k=1;
   while(sum<m)
   {
        ans++;
        k=sum;
        for(int i=l;i<=m;i++)
        {
            if(tx[i].l<=sum+1&&tx[i].r>k)
            {k=tx[i].r,l=i;}
        }
        sum=k;
   }
   printf("1\n%d",ans);
   //while(1);
}
int qty=yjn();
int main(){;}