输入输出样例

输入 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
5
2 2 2 1 2
2 3 1 2 4
2 0 1 1 1
2 3 4 3 3
3 2 1 2 1
输出 #1<button class="copy&#45;btn lfe&#45;form&#45;sz&#45;middle" data&#45;v&#45;370e72e2="" data&#45;v&#45;52f2d52f="" type="button">复制</button> 
5
14

 

 思路

　　易发现可以把人和任务分成两个阵营

　　这样就是一个标准的二分图

　　对于这个二分图跑最小费用最大流和最大费用最小流即可

　　把 S 到每个人的容量都设置为1即可保证每个人只做一件事

　　对于每个人到每个任务的花费自然是 Cij

 

CODE

 

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 #define eps 1e-8
  4 #define pi acos(-1.0)
  5 
  6 using namespace std;
  7 typedef long long LL;
  8 const int maxn = 1e5 +7;
  9 const int inf  = 0x3f3f3f3f;
 10 
 11 int n, m, s, t;
 12 int head[maxn],pre[maxn],inq[maxn],dis[maxn];
 13 int a[maxn];
 14 int cnt = 1;
 15 int path[2][maxn];
 16 int mincost = 0, maxflow = 0;
 17 struct edge {
 18     int u,to,nxt,w,c;
 19 }e[maxn << 1];
 20 int tot[5];
 21 
 22 template<class T>inline void read(T &res)
 23 {
 24     char c;T flag=1;
 25     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 26     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 27 }
 28 
 29 inline void BuildGraph(int u, int v, int w, int cost)
 30 {
 31     e[++cnt] = (edge){u, v, head[u], w,  cost}, head[u] = cnt;
 32     e[++cnt] = (edge){v, u, head[v], 0, -cost}, head[v] = cnt;///反向边
 33 }
 34 
 35 queue<int> q;
 36 
 37 inline void init() {
 38     memset(head, 0, sizeof(head));
 39     memset(pre, 0, sizeof(pre));
 40     memset(inq, 0, sizeof(inq));
 41     memset(dis, 0, sizeof(dis));
 42     memset(e, 0, sizeof(e));
 43     while(!q.empty()) {
 44         q.pop();
 45     }
 46     mincost = maxflow = 0;
 47     cnt = 1;
 48 }
 49 
 50 bool SPFA(int x)
 51 {
 52     memset(inq, 0, sizeof(inq));
 53     for(int i = s; i <= t; i++) {
 54         dis[i] = inf;
 55     }
 56     q.push(x);
 57     dis[x] = 0;
 58     inq[x] = 1;
 59     while(!q.empty()) {
 60         int u = q.front();
 61         q.pop();
 62         inq[u] = 0;
 63         for(int i = head[u]; i; i = e[i].nxt) {
 64             int v = e[i].to, w = e[i].c;
 65             if(e[i].w > 0) {
 66                 if(dis[u] + w < dis[v]) {
 67                     dis[v] = dis[u] + w;
 68                     pre[v] = i;
 69                     if(!inq[v]) {
 70                         q.push(v);
 71                         inq[v] = 1;
 72                     }
 73                 }
 74             }
 75         }
 76     }
 77     if(dis[t] == inf)
 78         return 0;
 79     return 1;
 80 }
 81 
 82 void MCMF()
 83 {
 84     while(SPFA(s)) {
 85         int temp = inf;
 86         for(int i = pre[t]; i; i = pre[e[i].u]) {
 87             temp = min(temp, e[i].w);
 88         }
 89         for(int i = pre[t]; i; i = pre[e[i].u]) {
 90             e[i].w   -= temp;
 91             e[i^1].w += temp;
 92             mincost += e[i].c * temp;
 93             //printf("e[%d].c:%d\n",i, e[i].c);
 94             //printf("ans:%d\n",ans);
 95         }
 96         //maxflow += temp;
 97     }
 98 }
 99 
100 int xx[107][107];
101 
102 int main()
103 {
104     //freopen("data.txt", "r", stdin);
105     read(n);
106     s = 0, t = n << 1 | 1;
107     for ( int i = 1; i <= n; ++i ) {
108         BuildGraph(s, i, 1, 0);
109         for ( int j = 1; j <= n; ++j ) {
110             read(xx[i][j]);
111             BuildGraph(i, j + n, 1, xx[i][j]);
112         }
113         BuildGraph(i + n, t, 1, 0);
114     }
115     MCMF();
116     int ans = mincost;
117     cout << ans << endl;
118     //dbg(maxflow);
119     init();
120     s = 0, t = n << 1 | 1;
121     for ( int i = 1; i <= n; ++i ) {
122         BuildGraph(s, i, 1, 0);
123         for ( int j = 1; j <= n; ++j ) {
124             BuildGraph(i, j + n, 1, -xx[i][j]);
125         }
126         BuildGraph(i + n, t, 1, 0);
127     }
128     MCMF();
129     ans = -mincost;
130     cout << ans << endl;
131     //dbg(maxflow);
132     return 0;
133 }
View Code

 

 

 

#include  < bits/stdc++.h >
#define  dbg( x ) cout  <<  #x  <<  " = "  << x  << endl
#define  eps  1 e - 8
#define  pi  acos( - 1.0 )

using  namespace std ;
typedef  long  long LL ;
const  int maxn  =  1 e 5  + 7 ;
const  int inf   =  0x 3f3f3f3f ;

int n , m , s , t ;
int  head [maxn ], pre [maxn ], inq [maxn ], dis [maxn ];
int  a [maxn ];
int cnt  =  1 ;
int  path [ 2 ][maxn ];
int mincost  =  0 , maxflow  =  0 ;
struct edge  {
     int u ,to ,nxt ,w ,c ;
} e [maxn  <<  1 ];
int  tot [ 5 ];

template < class T > inline  void  read(T  & res )
{
     char c ;T flag = 1 ;
     while((c = getchar()) < ' 0 ' ||c > ' 9 ' )if(c == ' - ' )flag =- 1 ;res =c - ' 0 ' ;
     while((c = getchar()) >= ' 0 ' &&c <= ' 9 ' )res =res * 10 +c - ' 0 ' ;res *=flag ;
}

inline  void  BuildGraph( int  u ,  int  v ,  int  w ,  int  cost )
{
     e [ ++cnt ]  =  (edge ){u , v ,  head [u ], w ,  cost },  head [u ]  = cnt ;
     e [ ++cnt ]  =  (edge ){v , u ,  head [v ],  0 ,  -cost },  head [v ]  = cnt ; ///反向边
}

queue <int> q ;

inline  void  init()  {
     memset(head ,  0 ,  sizeof (head ));
     memset(pre ,  0 ,  sizeof (pre ));
     memset(inq ,  0 ,  sizeof (inq ));
     memset(dis ,  0 ,  sizeof (dis ));
     memset(e ,  0 ,  sizeof (e ));
     while( ! q .empty())  {
         q .pop();
     }
    mincost  = maxflow  =  0 ;
    cnt  =  1 ;
}

bool  SPFA( int  x )
{
     memset(inq ,  0 ,  sizeof (inq ));
     for( int i  = s ; i  <= t ; i ++ )  {
         dis [i ]  = inf ;
     }
     q .push(x );
     dis [x ]  =  0 ;
     inq [x ]  =  1 ;
     while( ! q .empty())  {
         int u  =  q .front();
         q .pop();
         inq [u ]  =  0 ;
         for( int i  =  head [u ]; i ; i  =  e [i ]. nxt )  {
             int v  =  e [i ]. to , w  =  e [i ]. c ;
             if( e [i ]. w  >  0 )  {
                 if( dis [u ]  + w  <  dis [v ])  {
                     dis [v ]  =  dis [u ]  + w ;
                     pre [v ]  = i ;
                     if( ! inq [v ])  {
                         q .push(v );
                         inq [v ]  =  1 ;
                     }
                 }
             }
         }
     }
     if( dis [t ]  == inf )
         return  0 ;
     return  1 ;
}

void  MCMF()
{
     while(SPFA(s ))  {
         int temp  = inf ;
         for( int i  =  pre [t ]; i ; i  =  pre [ e [i ]. u ])  {
            temp  =  min(temp ,  e [i ]. w );
         }
         for( int i  =  pre [t ]; i ; i  =  pre [ e [i ]. u ])  {
             e [i ]. w    -= temp ;
             e [i ^ 1 ]. w  += temp ;
            mincost  +=  e [i ]. c  * temp ;
            //printf("e[%d].c:%d\n",i, e[i].c);
            //printf("ans:%d\n",ans);
         }
        //maxflow += temp;
     }
}

int  xx [ 107 ][ 107 ];

int  main()
{
    //freopen("data.txt", "r", stdin);
     read(n );
    s  =  0 , t  = n  <<  1  |  1 ;
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         BuildGraph(s , i ,  1 ,  0 );
         for  (  int j  =  1 ; j  <= n ;  ++j  )  {
             read( xx [i ][j ]);
             BuildGraph(i , j  + n ,  1 ,  xx [i ][j ]);
         }
         BuildGraph(i  + n , t ,  1 ,  0 );
     }
     MCMF();
     int ans  = mincost ;
    cout  << ans  << endl ;
    //dbg(maxflow);
     init();
    s  =  0 , t  = n  <<  1  |  1 ;
     for  (  int i  =  1 ; i  <= n ;  ++i  )  {
         BuildGraph(s , i ,  1 ,  0 );
         for  (  int j  =  1 ; j  <= n ;  ++j  )  {
             BuildGraph(i , j  + n ,  1 ,  - xx [i ][j ]);
         }
         BuildGraph(i  + n , t ,  1 ,  0 );
     }
     MCMF();
    ans  =  -mincost ;
    cout  << ans  << endl ;
    //dbg(maxflow);
     return  0 ;
}