우 객 다 교 5 차 E (비용 흐름)

링크:https://www.nowcoder.com/acm/contest/143/E 우 객 망 
시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K 64bit IO 포맷:% lld
제목 설명
Nowcoder University has 4n students and n dormitories ( Four students per dormitory). Students numbered from 1 to 4n.
And in the first year, the i-th dormitory 's students are (x1[i],x2[i],x3[i],x4[i]), now in the second year, Students need to decide who to live with.
In the second year, you get n tables such as (y1,y2,y3,y4) denote these four students want to live together.
Now you need to decide which dormitory everyone lives in to minimize the number of students who change dormitory.
입력 설명:

The first line has one integer n.

Then there are n lines, each line has four integers (x1,x2,x3,x4) denote these four students live together in the first year

Then there are n lines, each line has four integers (y1,y2,y3,y4) denote these four students want to live together in the second year

출력 설명:

Output the least number of students need to change dormitory.

예시 1
입력
복제 하 다.

2
1 2 3 4
5 6 7 8
4 6 7 8
1 2 3 5

출력
복제 하 다.

2

설명 하 다.

Just swap 4 and 5

비고:

1<=n<=100

1<=x1,x2,x3,x4,y1,y2,y3,y4<=4n

It's guaranteed that no student will live in more than one dormitories.

각 방 을 하나의 점 으로 보고 두 개의 점 으로 뜯 어 라.
i 방과 j 방 의 연결 비용 은 서로 다른 숫자의 개수 이다
원점 을 하나 만 들 고, 송금 점 하 나 를 만 들 면 비용 흐름 을 달 릴 수 있다.

#include
#define mp make_pair
#define fir first
#define se second
#define ll long long
#define pb push_back
using namespace std;
const int maxn=2e5+10;
const ll mod=1e9+7;
const int maxm=1e6+10;
const double eps=1e-7;
const int inf=0x3f3f3f3f;
const double pi = acos (-1.0);
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int to, next, cap, flow, cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N; //     ，     0~N-1
void init(int n)
{
    N = n;
    tol = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost)
{
    edge[tol]. to = v;
    edge[tol]. cap = cap;
    edge[tol]. cost = cost;
    edge[tol]. flow = 0;
    edge[tol]. next = head[u];
    head[u] = tol++;
    edge[tol]. to = u;
    edge[tol]. cap = 0;
    edge[tol]. cost = -cost;
    edge[tol]. flow = 0;
    edge[tol]. next = head[v];
    head[v] = tol++;
}
bool spfa(int s, int t)
{
    queueq;
    for(int i = 0; i < N; i++)
    {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1; i = edge[i]. next)
        {
            int v = edge[i]. to;
            if(edge[i]. cap > edge[i]. flow &&
                    dis[v] > dis[u] + edge[i]. cost )
            {
                dis[v] = dis[u] + edge[i]. cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1) return false;
    else return true;
}
//       ， cost       
int minCostMaxflow(int s, int t, int &cost)
{
    int flow = 0;
    cost = 0;
    while(spfa(s,t))
    {
        int Min = INF;
        for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])
        {
            if(Min > edge[i]. cap - edge[i]. flow)
                Min = edge[i]. cap - edge[i]. flow;
        }
        for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])
        {
            edge[i]. flow += Min;
            edge[i^1]. flow -= Min;
            cost += edge[i]. cost * Min;
        }
        flow += Min;
    }
    return flow;
}
int n;
int x[150][5],y[150][5];
int main(){
    scanf("%d",&n);
    init(2*n+2);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=4;j++){
            scanf("%d",&x[i][j]);
        }
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=4;j++){
            scanf("%d",&y[i][j]);
        }
    }
    for (int i=1;i<=n;i++){
        addedge(0,i,1,0);
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            int num=0;
            for (int a=1;a<=4;a++){
                int flag=0;
                for (int b=1;b<=4;b++){
                    if (x[i][a]==y[j][b]){
                        flag=1;
                        break;
                    }
                }
                if (!flag){
                    num++;
                }
            }
           // cout<