題意就是N個(gè)學(xué)校，每個(gè)學(xué)校有一個(gè)編號(hào)，編號(hào)可以重復(fù)。現(xiàn)在要求每個(gè)學(xué)校有一個(gè)獨(dú)立的編號(hào)，但是每個(gè)學(xué)校可以接受的編號(hào)有一個(gè)范圍，在這個(gè)范圍內(nèi)，編號(hào)每變動(dòng)1將付出的話費(fèi)是D。求是否有可行方案并給出最小花費(fèi)。
顯然X部分是所有的學(xué)校，Y部分是新的編號(hào)，按順序我們把學(xué)校設(shè)置成1—N,設(shè)置超級(jí)源點(diǎn)s,s向每個(gè)X側(cè)的節(jié)點(diǎn)連一條費(fèi)用是0，流量是1的邊，把他們對(duì)應(yīng)的編號(hào)設(shè)置成節(jié)點(diǎn)N+1- 2*N,X部和Y部的邊用計(jì)算出來的花費(fèi)連邊，流量是1，Y部每個(gè)節(jié)點(diǎn)向t連一條費(fèi)用是0流量是1的邊，求最小費(fèi)用最大流即可。
模板就不貼了，構(gòu)圖部分代碼如下：
void creat(int n,int s,int t)
{
flowsum=0;
int a,b,c,d;
int i;
for(i=1;i<=n;i++)
{
insert(s,i,1,0);
insert(i+n,t,1,0);
scanf("%d%d%d%d",&a,&b,&c,&d);
int j;
for(j=b;j<=c;j++)
{
insert(i,j+n,1,abs(j-a)*d);
}
}
}
void init(int n)
{
int i;
for(i=0;i<n;i++)
adj[i]=NULL;
len=0;
}
int main()
{
int n;
int s,t;
scanf("%d",&n);
init(2*n+2);
s=0;
t=2*n+1;
creat(n,s,t);
int ans=mincostflow(t+1,s,t);
if(flowsum!=n)
printf("NIE\n");
else
printf("%d\n",ans);
return 0;
}