POJ 3686 最小权匹配
题意:有N个工作,可以由M个工厂完成,但是每个工厂一次只能完成一个工作,并且完成这个工作之前不能换别的工作。问完成时间的平均值最少是多少。思路:很神奇的建图,完全是突破天际了。
偶然间看到一种写法,突然感觉这个代码风格有点像魏神的,然后去他博客里一搜,居然真是。
来个传送门神牛博客
/*****以下转自上述博客********/
假设某个机器处理了k个玩具,那么对于这些玩具,有两种时间,一种是真正处理的时间,一种是等待的时间,等待的时间就是之前所有处理的玩具的时间,
假设这k个玩具真正用在加工的时间分为a1,a2,a3...ak, 那么每个玩具实际的时间是加工的时间+等待时间,分别为
a1, a1+a2, a1+a2+a3.......a1+a2+...ak
求和之后变为 a1 *k + a2 * (k - 1) + a3 * (k - 2).... + ak
这时就发现,每个玩具之间的实际时间可以分开来算 然后求和了。
因为对每个机器,最多可以处理n个玩具,所以可以拆成n个点,1~n分别代表某个玩具在这个机器上倒数第几个被加工的
所以我们对于每个玩具i,机器j中拆的每个点k,连接一条z[i][j]*k权值的边。
/******转完收工*******/
建完图就是最小权匹配了。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; /*********************************************/ #define N 2555 #define eps 1e-8 int n , m ; int Map[55][N] ; int lx[N] , ly[N] ,visx[N] , visy[N] , linkx[N] , linky[N] ; //int fk[N][N] ; int h ; int find(int now) { visx[now] = 1 ; for (int i = 1 ; i <= h ; i ++ ) { if(!visy[i] && Map[now][i] - lx[now] - ly[i] == 0) { visy[i] = 1 ; if(linky[i] == -1 || find(linky[i])) { linkx[now] = i ; linky[i] = now ; return 1 ; } } } return 0 ; } int KM() { mem(linky ,-1) ; mem(ly , 0) ; for (int i = 1 ; i <= n ; i ++ ) { while(1) { // bug ; mem(visx, 0) ;mem(visy ,0) ; if(find(i))break ; int d = inf ; for (int j = 1 ; j <= n ; j ++ ) if(visx[j]) for (int k = 1 ; k <= h ; k ++ ) if(!visy[k]) d = min(d , Map[j][k] - lx[j] - ly[k]) ; for (int j = 1 ; j <= n ; j ++ ){ if(visx[j])lx[j] += d ; } for (int j = 1 ; j <= h ; j ++ ){ if(visy[j])ly[j] -= d ; } } } int ans = 0 ; for (int i = 1 ; i <= h ; i ++ ){ if(linky[i] != -1)ans += Map[linky[i]][i] ; } return ans ; } int main() { int t ; cin >> t ; while(t -- ) { cin >> n >> m ; mem(Map ,0) ; int tt ; for (int i = 1 ; i <= n ; i ++ ) { for (int j = 1 ; j <= m ; j ++ ) { scanf("%d",&tt) ; for (int k = 1 ; k <= n ; k ++ ){ Map[i][n * (j - 1) + k] = k * (tt) ; } } } h = n * m ; for (int i = 1 ; i <= n ; i ++ ){ lx[i] = inf ; for (int j = 1 ; j <= h ; j ++ ){ lx[i] = min(lx[i] , Map[i][j]) ; } } int ans = KM() ; printf("%.6f\n",ans * 1.0 / n) ; } return 0 ; }
补充:软件开发 , C++ ,