URAL1076[Trash]

第一次写最小费用最大流(以前只写过最大流),第二次写bellman-ford加优化(即SPFA)。


然后一次AC,呵呵。


还有感谢WSC提供的解题思路。


CODE:


/*


PROGRAM: $PROGRAM


AUTHOR: Su Jiao


DATE: 2010-4-10


DESCRIPTION:


$DESCRIPTION


*/


#include <iostream>


using std::cin;


using std::cout;


#include <fstream>


using std::ifstream;


using std::ofstream;


#include <sstream>


using std::stringstream;


using std::endl;


#include <vector>


using std::vector;


#include <string>


using std::string;


#include <stack>


using std::stack;


#include <queue>


using std::queue;


using std::priority_queue;


#include <set>


using std::set;


#include <map>


using std::map;


using std::pair;


using std::make_pair;


#include <algorithm>


using std::sort;


using std::min;


#include <cassert>


//using std::assert;


 


class Application


{


      static const int oo=1<<20;


      int N;


      vector<vector<int> > data;


      vector<vector<int> > cost;


      vector<vector<int> > c;


      int answer;


      void max_flow_with_min_cost(const int& S,const int& T)


      {


           static const int NOPRE=-1;


           answer=0;


           vector<vector<int> > f((N+1)*2,vector<int>((N+1)*2,0));


           for (;;)


           {


               vector<int> pre((N+1)*2,NOPRE);


               vector<int> dis((N+1)*2,oo);


               queue<int> q;


               vector<bool> inq((N+1)*2,false);


               pre[S]=S;


               dis[S]=0;


               q.push(S);


               inq[S]=true;


               while (!q.empty())


               {


                     int now=q.front();


                     for (int i=0;i<(N+1)*2;i++)


                         if ((f[now][i]<c[now][i])


                             &&(dis[i]>dis[now]+cost[now][i]))


                         {


                            pre[i]=now;


                            dis[i]=dis[now]+cost[now][i];


                            if (!inq[i])


                            {


                               q.push(i);


                               inq[i]=true;


                            }


                         }


                     q.pop();


                     inq[now]=false;


               }


               if (pre[T]==NOPRE) break;


               else


               {


                   int delta=oo;


                   int now;


                   now=T;


                   for (;;)


                   {


                       delta=min(delta,c[pre[now]][now]-f[pre[now]][now]);


                       now=pre[now];


                       if (pre[now]==now) break;


                   }


                   now=T;


                   for (;;)


                   {


                       f[pre[now]][now]+=delta;


                       f[now][pre[now]]-=delta;


                       now=pre[now];


                       if (pre[now]==now) break;


                   }


                   answer+=delta*dis[T];


               }


           }


      }


      public:


      Application()


      {


                   cin>>N;


                   data.resize(N,vector<int>(N));


                   for (int i=0;i<N;i++)


                       for (int j=0;j<N;j++)


                           cin>>data[i][j];


      }


      int run()


      {


          const int S=N*2,T=N*2+1;


          cost.resize((N+1)*2,vector<int>((N+1)*2,oo));


          for (int i=0;i<N;i++)


          {


              int sum=0;


              for (int j=0;j<N;j++)


                  sum+=data[i][j];


              for (int j=0;j<N;j++)


              {


                  cost[i][N+j]=sum-data[i][j];


                  cost[N+j][i]=data[i][j]-sum;


              }


          }


          for (int i=0;i<N;i++)


          {


              cost[S][i]=0;


              cost[i][S]=0;


          }


          for (int i=0;i<N;i++)


          {


              cost[i+N][T]=0;


              cost[T][i+N]=0;


          }


          c.resize((N+1)*2,vector<int>((N+1)*2,0));


          for (int i=0;i<N;i++)


              for (int j=0;j<N;j++)


                  c[i][j+N]=oo;


          for (int i=0;i<N;i++)


              c[S][i]=1;


          for (int i=0;i<N;i++)


              c[i+N][T]=1;


          max_flow_with_min_cost(S,T);


          cout<<answer<<endl;


          return 0;


      }


};


 


int main()


{


    Application app;


    return app.run();


}