HDU 3488 Tour 最大权匹配

链接： ?pid=3488

题意：一个图n个点m条有向边，一个人要到所有的点，他可以从一个点出发，走一个环（不可以自环）再回到起点，他可以走多个环但是不可以走之前走过的点（回到起点不算）。问走完所有点的最小的花费是多少。

建立二分图X集合和Y集合都是节点，目的是求每个点都只有一个出度和一个入读，且必须有一个出度和一个入度，就是二分图的完美匹配，，由于需要求的是最小权的完美匹配，用到KM算法。

/*——————— #headfile——————–*/#include <algorithm>#include <iostream>#include <sstream>#include <cstring>#include <cstdlib>#include <cassert>#include <cstdio>#include <vector>#include <cmath>#include <queue>#include <stack>#include <set>#include <map>/*———————-#define———————-*/#define DRII(X,Y) int (X),(Y);scanf("%d%d",&(X),&(Y))#define EXP 2.7182818284590452353602874713527#define CASET int _;cin>>_;while(_–)#define RII(X, Y) scanf("%d%d",&(X),&(Y))#define DRI(X) int (X);scanf("%d", &X)#define mem(a,b) memset(a,b,sizeof(a))#define rep(i,n) for(int i=0;i<n;i++)#define ALL(X) (X).begin(),(X).end()#define INFL 0x3f3f3f3f3f3f3f3fLL#define RI(X) scanf("%d",&(X))#define SZ(X) ((int)X.size())#define PDI pair<double,int>#define rson o<<1|1,m+1,r#define PII pair<int,int>#define MAX 0x3f3f3f3f#define lson o<<1,l,m#define MP make_pair#define PB push_back#define SE second#define FI firsttypedef long long ll;template<class T>T MUL(T x,T y,T P){T F1=0;while(y){if(y&1){F1+=x;if(F1<0||F1>=P)F1-=P;}x<<=1;if(x<0||x>=P)x-=P;y>>=1;}return F1;}template<class T>T POW(T x,T y,T P){T F1=1;x%=P;while(y){if(y&1)F1=MUL(F1,x,P);x=MUL(x,x,P);y>>=1;}return F1;}template<class T>T gcd(T x,T y){if(y==0)return x;T z;while(z=x%y)x=y,y=z;return y;}#define DRIII(X,Y,Z) int (X),(Y),(Z);scanf("%d%d%d",&(X),&(Y),&(Z))#define RIII(X,Y,Z) scanf("%d%d%d",&(X),&(Y),&(Z))const double pi = acos(-1.0);const double eps = 1e-6;const ll mod = 1000000007ll;const int M = 100005;const int N = 215;using namespace std;/*———————-Main————————-*/int n, m;int mc[N], lx[N], ly[N], sk[N];int vx[N], vy[N], w[N][N];bool dfs(int x) {vx[x] = 1;for(int y = 1; y <= m; y++) {if(vy[y]) continue;int tmp = lx[x] + ly[y] – w[x][y];if(tmp == 0) {vy[y] = 1;if(mc[y] == -1 || dfs(mc[y])) {mc[y] = x;return 1;}} else sk[y] = min(sk[y], tmp);}return 0;}int KM() {mem(mc, -1);mem(ly, 0);for(int i = 1; i <= n; i++) {lx[i] = -1e9;for(int j = 1; j <= m; j++) {lx[i] = max(lx[i], w[i][j]);}}for(int x = 1; x <= n; x++) {for(int i = 1; i <= m; i++) sk[i] = 1e9;while(1) {mem(vx, 0);mem(vy, 0);if(dfs(x)) break;int d = 1e9;for(int i = 1; i <= m; i++) if(!vy[i]) d = min(d, sk[i]);for(int i = 1; i <= n; i++) if(vx[i]) lx[i] -= d;for(int i = 1; i <= m; i++) {if(vy[i]) ly[i] += d;else sk[i] -= d;}}}int res = 0;for(int i = 1; i <= m; i++) {if(mc[i] != -1) res += w[mc[i]][i];}return res;}void solve() {int q;RII(n, q);m = n;for(int i = 1; i <= n; i++) {for(int j = 1; j <= m; j++) {w[i][j] = -1e9;}}for(int i = 0; i < q; i++) {DRIII(U, V, W);w[U][V] = max(w[U][V], -W);}printf("%d\n", -KM());}int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);CASETsolve();return 0;}

谁的指间滑过了千年时光；谁在反反复复中追问可曾遗忘；

相关文章：

你感兴趣的文章：

标签云：