[关闭]
@suixinhita 2017-10-25T11:55:56.000000Z 字数 4919 阅读 1133

代码

图论

1

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int N=105;
  7. const int M=105;
  8. struct data{
  9.     int next,to;
  10. }e[1000005];
  11. int head[N],gs;
  12. char ans[N];
  13. int in[N],n;
  15. int len[M],cnt;
  16. char s[M][M];
  17. void add(int fr,int to)
  18. {
  19.     e[++gs].to=to;e[gs].next=head[fr],head[fr]=gs;in[to]++;
  20. }
  22. bool topsort()
  23. {
  24.     queue<int> q;
  25.     for(int i=1;i<=26;++i)  if(!in[i])  q.push(i);
  26.     while(!q.empty())
  27.     {
  28.         int u=q.front();q.pop();ans[++cnt]='a'+u-1;
  29.         for(int i=head[u];i;i=e[i].next)
  30.         {
  31.             int v=e[i].to;
  32.             if(--in[v]==0)  q.push(v);
  33.         }
  34.     }
  35.     for(int i=1;i<=26;++i)  if(in[i])   return 0;
  36.     return 1;
  37. }
  39. void solve()
  40. {
  41.     for(int i=1;i<n;++i)
  42.     {
  43.         for(int j=i+1;j<=n;++j)
  44.         {
  45.             int l1=len[i],l2=len[j];
  46.             for(int k=1;k<=l1;++k)
  47.             if(k>l2)    
  48.             {
  49.                 puts("Impossible");return;
  50.             }
  51.             else    if(s[i][k]!=s[j][k])
  52.             {
  53.                 add(s[i][k]-'a'+1,s[j][k]-'a'+1);
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.     if(!topsort())
  59.     {
  60.         puts("Impossible");return;
  61.     }
  62.     for(int i=1;i<=cnt;++i) printf("%c",ans[i]);
  63. }
  65. int main()
  66. {
  67. //  freopen("1.txt","r",stdin);
  68.     scanf("%d",&n);
  69.     for(int i=1;i<=n;++i)
  70.     {
  71.         scanf("%s",s[i]+1);
  72.         len[i]=strlen(s[i]+1);
  73.     }
  74.     solve();
  75.     return 0;
  76. }

2

  1. #include<queue>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #define ll long long
  5. using namespace std;
  6. const int N=1e6+5;
  7. struct data{
  8.     int to,next;
  9.     ll v;
  10. }e[N<<1];
  11. int head[N],gs,n,q,x,y,v;
  12. int in[N],out[N];
  13. ll c[N],U[N];
  15. void add(int fr,int to,ll v)
  16. {
  17.     e[++gs].to=to,e[gs].next=head[fr],head[fr]=gs,e[gs].v=v,in[to]++,out[fr]++;
  18. }
  20. void topsort()
  21. {
  22.     queue<int> q;
  23.     for(int i=1;i<=n;++i)
  24.         if(in[i]==0)    q.push(i);
  26.     while(!q.empty())
  27.     {
  28.         int u=q.front();q.pop();
  29.         for(int i=head[u];i;i=e[i].next)
  30.         {
  31.             int v=e[i].to;
  32.             c[v]+=e[i].v*c[u];
  33.             if(--in[v]==0)  q.push(v),c[v]-=U[v],c[v]=c[v]<0?0:c[v];
  34.         }
  35.     }
  36.     int flag=1;
  37.     for(int i=1;i<=n;++i)
  38.         if(out[i]==0&&c[i]>0)
  39.             flag=0,printf("%d %lld\n",i,c[i]);
  40.     if(flag)    puts("NULL");
  41. }
  43. inline int read()
  44. {
  45.     int x=0,y=1;char c=getchar();
  46.     while(c<'0'||c>'9') 
  47.     {   
  48.         if(c=='-')  y=-1;
  49.         c=getchar();
  50.     }
  51.     while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
  52.     return x*y;
  53. }
  55. int main()
  56. {
  57. //  freopen("1.txt","r",stdin);
  58.     n=read(),q=read();
  59.     for(int i=1;i<=n;++i)   c[i]=read(),U[i]=read();
  60.     for(int i=1;i<=q;++i)   
  61.     {
  62.         x=read(),y=read(),v=read();
  63.         add(x,y,v);
  64.     }
  65.     topsort();
  66.     return 0;
  67. }

3

  1. #include<stack>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int N=1005;
  7. const int inf=0x3f3f3f3f;
  8. stack<int> s[2];
  9. struct data{
  10.     int to,next;
  11. }e[N];
  12. int head[N],gs;
  13. int a[N],col[N],n,mn[N];
  15. void add(int fr,int to)
  16. {
  17.     //printf("%d %d\n",fr,to);
  18.     e[++gs].to=to,e[gs].next=head[fr],head[fr]=gs;
  19. }
  21. void init()
  22. {
  23.     a[n+1]=inf;
  24.     for(int i=1;i<=n+1;++i) mn[i]=inf;  
  25.     for(int i=n;i>=1;--i)
  26.         mn[i]=min(mn[i+1],a[i]);
  27.     for(int i=1;i<=n;++i)
  28.         for(int j=i+1;j<=n;++j)
  29.             if(a[i]<a[j]&&mn[j+1]<a[i]) add(i,j),add(j,i);
  31.     memset(col,-1,sizeof(col));     
  32. }
  34. bool dfs(int u,int c)
  35. {
  36.     col[u]=c;
  37.     for(int i=head[u];i;i=e[i].next)
  38.     {
  39.         int v=e[i].to;
  40.         bool flag=1;
  41.         if(col[v]==-1)  
  42.         {
  43.             flag=dfs(v,c^1);
  44.             if(!flag)   return 0;
  45.         }
  46.         else    if(col[v]==c)   return 0;
  47.     }
  48.     return 1;
  49. }
  51. inline int read()
  52. {
  53.     int x=0;char c=getchar();
  54.     while(c<'0'||c>'9') c=getchar();
  55.     while(c>='0'&&c<='9')   x=x*10+c-'0',c=getchar();
  56.     return x;
  57. }
  59. int main()
  60. {
  61. //  freopen("1.txt","r",stdin);
  62. //  freopen("11.txt","w",stdout);
  63.     n=read();
  64.     for(int i=1;i<=n;++i)   a[i]=read();
  65.     init();
  66.     for(int i=1;i<=n;++i)   
  67.         if(col[i]==-1)  if(dfs(i,0)==0) 
  68.         {
  69.             puts("0");return 0;
  70.         }
  71.     int now=1;s[0].push(inf),s[1].push(inf);
  72.     for(int i=1;i<=n;++i)
  73.     {
  74.         if(col[i]==0)   printf("a "),s[0].push(a[i]);
  75.         else    if(col[i]==1)   printf("c "),s[1].push(a[i]);
  76.         while(s[0].top()==now||s[1].top()==now)
  77.         {
  78.             if(s[0].top()==now) printf("b "),s[0].pop();
  79.             else    printf("d "),s[1].pop();
  80.             now++;
  81.         }
  82.     }
  83.     return 0;
  84. }

4

  1. #include<queue>
  2. #include<cstdio>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  6. const int N=10005;
  7. const int M=1000005;
  8. const int inf=0x3f3f3f3f;
  9. struct data{
  10.     int  to,next,f;
  11. }e[M];
  12. int head[N],gs=1,s,t;
  13. bool map[105][105];
  14. int l[105][105],r[105][105],m,n;
  15. int fx[5],fy[5];
  16. char S[105];
  18. void add(int fr,int to,int f)
  19. {
  20. //  printf("%d %d\n",fr,to);
  21.     e[++gs].to=to,e[gs].f=f,e[gs].next=head[fr],head[fr]=gs;
  22.     e[++gs].to=fr,e[gs].f=0,e[gs].next=head[to],head[to]=gs;
  23. }
  25. int dis[N],now[N];
  26. bool bfs()
  27. {
  28.     queue<int> q;
  29.     memset(dis,-1,sizeof(dis));
  30.     dis[s]=0,q.push(s);
  31.     while(!q.empty())
  32.     {
  33.         int u=q.front();q.pop();
  34.         for(int i=head[u];i;i=e[i].next)
  35.         {
  36.             int v=e[i].to;
  37.             if(!e[i].f) continue;
  38.             if(dis[v]==-1)
  39.             {
  40.                 dis[v]=dis[u]+1;
  41.                 q.push(v);
  42.             }
  43.         }
  44.     }
  45.     if(dis[t]==-1)  return 0;
  46.     else    return 1;
  47. }
  49. int dfs(int u,int f)
  50. {
  51.     if(u==t)    return f;
  52.     int ff,k,su=0;
  53.     for(int i=now[u];i;i=e[i].next)
  54.     {
  55.         int v=e[i].to;
  56.         if(dis[v]==dis[u]+1)
  57.         {
  58.             ff=min(e[i].f,f-su);
  59.             k=dfs(v,ff);
  60.             su+=k;
  61.             e[i].f-=k,e[i^1].f+=k;
  62.             if(e[i].f)  now[u]=i;
  63.             if(su==f)   return su;
  64.         }
  65.     }
  66.     if(!su) dis[u]=-1;
  67.     return su;
  68. }
  70. int dinic()
  71. {
  72.     int an=0;
  73.     while(bfs())
  74.     {
  75.         for(int i=s;i<=t;++i)   now[i]=head[i];
  76.         an+=dfs(s,inf);
  77.     }
  78.     return an;
  79. }
  81. void build()
  82. {
  83.     int cntl=0,cntr=n*m;
  84.     for(int i=1;i<=n;++i)
  85.         for(int j=1;j<=m;++j)
  86.         {
  87.             l[i][j]=++cntl;
  88.             r[i][j]=++cntr;
  89.         }
  90.     for(int i=1;i<=n;++i)
  91.         for(int j=1;j<=m;++j)
  92.             for(int k=1;k<=4;++k)
  93.             {
  94.                 int x=i+fx[k],y=j+fy[k];
  95.                 if(x<1||x>n)    continue;
  96.                 if(y<1||y>m)    continue;
  97.                 if((!map[i][j])&&(!map[x][y]))  add(l[i][j],r[x][y],1);
  98.             }
  99.     s=0,t=++cntr;
  100.     for(int i=1;i<=n;++i)
  101.         for(int j=1;j<=m;++j)
  102.             if(!map[i][j])  add(s,l[i][j],1),add(r[i][j],t,1);
  103. }
  105. int main()
  106. {
  107. //  freopen("1.txt","r",stdin);
  108. //  freopen("11.txt","w",stdout);
  109.     int R,C;int tot=0;
  110.     scanf("%d%d%d%d",&n,&m,&R,&C);
  111.     for(int i=1;i<=n;++i)
  112.     {
  113.         scanf("%s",S+1);
  114.         for(int j=1;j<=m;++j)   if(S[j]=='x')   map[i][j]=1,tot++;
  115.     }
  116.     fx[1]=R,fx[2]=C,fx[3]=R,fx[4]=C;
  117.     fy[1]=C,fy[2]=R,fy[3]=-C,fy[4]=-R;
  118.     build();
  119.     int ans=dinic();
  120.     printf("%d\n",m*n-tot-ans);
  121.     return 0;
  122. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注