poj 3422 Kaka's Matrix Travels

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<queue>
  4 #include<cmath>
  5 #include<algorithm>
  6 #define maxn 100000
  7 using namespace std;
  8 
  9 const int inf=1<<30;
 10 struct node
 11 {
 12     int u,v,w,f,c,next;
 13 }p[maxn];
 14 int e=0,head[maxn],g[100][100],n,k,s,t,dis[maxn],pre[maxn],ans=0;
 15 bool vis[maxn];
 16 
 17 void add(int u,int v,int w,int c)
 18 {
 19     p[e].u=u;p[e].v=v;p[e].w=w;p[e].f=0;p[e].c=c;
 20     p[e].next=head[u];head[u]=e++;
 21     p[e].u=v;p[e].v=u;p[e].w=0;p[e].f=0;p[e].c=-c;
 22     p[e].next=head[v];head[v]=e++;
 23 }
 24 
 25 void mcmf()
 26 {
 27     for(;;)
 28     {
 29         memset(dis,-1,sizeof(dis));
 30         memset(pre,-1,sizeof(pre));
 31         dis[s]=0;
 32         memset(vis,0,sizeof(vis));
 33         queue<int>q;
 34         q.push(s);
 35         vis[s]=true;
 36         while(!q.empty())
 37         {
 38             int u=q.front();q.pop();
 39             vis[u]=false;
 40             for(int i=head[u];i!=-1;i=p[i].next)
 41             {
 42                 int j=p[i].v;
 43                 if(p[i].w>p[i].f&&(dis[j]<dis[u]+p[i].c))
 44                 {
 45                     dis[j]=dis[u]+p[i].c;
 46                     pre[j]=i;
 47                     if(!vis[j])
 48                     {
 49                         vis[j]=true;
 50                         q.push(j);
 51                     }
 52                 }
 53             }
 54         }
 55         if(dis[t]==-1) break;
 56         int a=inf;
 57         for(int i=pre[t]; i!=-1; i=pre[p[i].u])
 58         {
 59             a=min(a,p[i].w-p[i].f);
 60         }
 61         for(int i=pre[t]; i!=-1; i=pre[p[i].u])
 62         {
 63             p[i].f+=a;
 64             p[i^1].f-=a;
 65         }
 66         ans+=dis[t];
 67     }
 68 }
 69 int main()
 70 {
 71     while(scanf("%d%d",&n,&k)!=EOF)
 72     {
 73         for(int i=1; i<=n; i++)
 74         {
 75             for(int j=1; j<=n; j++)
 76             {
 77                 scanf("%d",&g[i][j]);
 78             }
 79         }
 80         e=0;
 81         s=0;
 82         t=2*n*n+1;
 83         memset(head,-1,sizeof(head));
 84         add(s,1,k,0);
 85         add(2*n*n,t,k,0);
 86         for(int i=1; i<=n; i++)
 87         {
 88             for(int j=1; j<=n; j++)
 89             {
 90                 int num=(i-1)*n+j;
 91                 add(num,num+n*n,1,g[i][j]);
 92                 add(num,num+n*n,inf,0);
 93                 if(j!=n)
 94                 {
 95                     add(num+n*n,num+1,inf,0);
 96                 }
 97                 if(i<n)
 98                 {
 99                     add(num+n*n,num+n,inf,0);
100                 }
101             }
102         }
103         ans=0;
104         mcmf();
105         printf("%d
",ans);
106     }
107     return 0;
108 }
View Code