Description：

有 $n$ 个人，最开始每个人有一个标号，可能有两个人标号相同，要把他们的编号替换成两两不同的，如果第 $i$ 个人原编号是 $m$ ，之后编号是 $m'$ ，那么要支付 $|m-m'|\times k_i$ 的代价，每个人编号有可行范围，最小化代价。

$1\le n \le 200$

Solution：

源点向每个人连容量为 $1$ 费用为 $0$ 的边，每个标号向汇点连容量为一，费用为零的边，每个人向可行范围内的点 $m'$ 连容量为 $1$ ，费用为 $k_i\times |m-m'|$ 的边，跑最小费用最大流即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n;

#define MAXN 210

struct edge

{

	int to,nxt,f,c;

}e[MAXN * MAXN * 2 + MAXN * 4];

int edgenum = 0;

int lin[MAXN << 1];

void add(int a,int b,int f,int c)

{

	e[edgenum].to = b;e[edgenum].f = f;e[edgenum].c =  c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

	e[edgenum].to = a;e[edgenum].f = 0;e[edgenum].c = -c;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

	return;

}

int s,t;

int d[MAXN << 1],pre[MAXN << 1],rate[MAXN << 1];

bool v[MAXN << 1];

#define INF 0x3f3f3f3f

bool SPFA()

{

	queue<int> q;

	memset(d,0x3f,sizeof(d));

	memset(pre,0,sizeof(pre));

	memset(rate,0x3f,sizeof(rate));

	q.push(s);

	d[s] = 0;

	v[s] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != -1;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].c && e[i].f)

			{

				d[e[i].to] = d[k] + e[i].c;

				pre[e[i].to] = i;

				rate[e[i].to] = min(rate[k],e[i].f);

				if(!v[e[i].to])

				{

					q.push(e[i].to);

					v[e[i].to] = true;

				}

			}

		}

	}

	return (d[t] != INF); 

}

int ans = 0,sum = 0;

void flow()

{

	for(int i = t;i != s;i = e[pre[i] ^ 1].to)

	{

		e[pre[i]].f -= rate[t];

		e[pre[i] ^ 1].f += rate[t];

	}

	ans += d[t] * rate[t];

	sum += rate[t];

	return;

}

void EK()

{

	while(SPFA())flow();

	return;

}

int main()

{

	memset(lin,-1,sizeof(lin));

	scanf("%d",&n);

	int m,a,b,k;

	s = 2 * n + 1;t = s + 1;

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d%d%d",&m,&a,&b,&k);

		add(s,i,1,0);add(i + n,t,1,0);

		for(int j = a;j <= b;++j)add(i,j + n,1,abs(m - j) * k);

	}

	EK();

	if(sum != n)puts("NIE");

	else cout << ans << endl;

	return 0;

}