题意：有n个寝室，每个寝室4个人，现在在搞搬寝室的活动，告诉你每个寝室之前的人员名单，和之后的人员名单，问最少需要几个人要搬寝室。

 

思路：

转化为最小费用最大流解决的二分图问题，对每个去年的宿舍，向每个今年的组合连一条边，权值为1，费用为需要搬的人数（4-相同的人数），源点到去年各点，今年各点到汇点，都连一条权值为1费用为0的最大流，跑一次费用流即可。

 

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             

, greater

>que;const ll mos = 0x7FFFFFFF; //2147483647const ll nmos = 0x80000000; //-2147483648const int inf = 0x3f3f3f3f;const ll inff = 0x3f3f3f3f3f3f3f3f; //18template

inline T read(T&x){ x=0;int f=0;char ch=getchar(); while (ch<'0'||ch>'9') f|=(ch=='-'),ch=getchar(); while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x=f?-x:x;}// #define _DEBUG; //*//#ifdef _DEBUGfreopen("input", "r", stdin);// freopen("output.txt", "w", stdout);#endif/*-----------------show time----------------*/int n,m;const int maxn =5009;const int max_edge = 40009;struct Edge{ int to,nxt = -1; ll val,cost;};Edge gEdges[max_edge*2];ll gHead[maxn],gPre[maxn],gDist[maxn],gPath[maxn];bool in[maxn];int gCount = 0;void addEdge(int u,int v,ll c,ll w){ gEdges[gCount].to = v; gEdges[gCount].val = c; gEdges[gCount].cost = w; gEdges[gCount].nxt = gHead[u]; gHead[u] = gCount++; gEdges[gCount].to = u; gEdges[gCount].val = 0; gEdges[gCount].cost = -1*w; gEdges[gCount].nxt = gHead[v]; gHead[v] = gCount++;}bool spfa(int s,int t){ // memset(gDist, inff, sizeof(gDist)); for(int i=0; i<=2*n+1; i++){ gDist[i] = inff; } memset(gPre , -1 , sizeof(gPre)); memset(in,false,sizeof(in)); queue

Q; Q.push(s); in[s] = true; gDist[s] = 0; while(!Q.empty()){ int u = Q.front(); Q.pop(); in[u] = false; for(int e = gHead[u]; e!=-1; e = gEdges[e].nxt){ int v = gEdges[e].to; if(gEdges[e].val>0 && gDist[v] > gDist[u] + gEdges[e].cost){ gDist[v] = gDist[u] + gEdges[e].cost; gPre[v] = u; gPath[v] = e; if(in[v]==false){ Q.push(v); in[v] = true; } } } } if(gPre[t]==-1)return false; else return true;}ll flow = 0;ll MinCostFlow(int s,int t){ ll cost = 0; while(spfa(s,t)){ ll f = inff; for(int u = t; u!=s; u = gPre[u]){ if(f > gEdges[gPath[u]].val) f = gEdges[gPath[u]].val; } flow += f; cost += 1ll*gDist[t] * f; for(int u=t; u!=s; u=gPre[u]){ gEdges[gPath[u]].val -= f; gEdges[gPath[u]^1].val += f; } } return cost;}struct room{ int a,b,c,d;}rm[maxn];int getw(int x,int y){ int res = 4; res -= (rm[x].a == rm[y].a ||rm[x].a == rm[y].b||rm[x].a == rm[y].c||rm[x].a == rm[y].d); res -= (rm[x].b == rm[y].a ||rm[x].b == rm[y].b||rm[x].b == rm[y].c||rm[x].b == rm[y].d); res -= (rm[x].c == rm[y].a ||rm[x].c == rm[y].b||rm[x].c == rm[y].c||rm[x].c == rm[y].d); res -= (rm[x].d == rm[y].a ||rm[x].d == rm[y].b||rm[x].d == rm[y].c||rm[x].d == rm[y].d); return res; }int main(){ memset(gHead,-1,sizeof(gHead)); int s,t; scanf("%d", &n); for(int i=1; i<=n*2; i++){ scanf("%d%d%d%d", &rm[i].a, &rm[i].b, &rm[i].c, &rm[i].d); } for(int i=1; i<=n; i++){ addEdge(0,i,1,0); addEdge(n+i,2*n+1,1,0); for(int j=1+n; j<=2*n; j++){ addEdge(i,j,1,getw(i,j)); } } ll cost = MinCostFlow(0,2*n+1); printf("%lld\n" ,cost); return 0;}