分配的任务中,和核心1在一起(在一起!!!)的在割完后设为和S在一起(啊咧咧,要受虐了QwQ),和核心2在一起的在割完后和M(明明是T好吧!!!)在一起,这样,如果两个任务不在一个核心要额外收费的话那么就在两个节点间连一条双向边,最后求一次最小割(就是最大流),建图见代码,AC快速通道看这里(明明是这里!)
建图提示:
吐槽:Poj的网速怎么了?这么慢?
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int maxn=20005,maxm=(20005+200005)*10+10;
struct edge{int t,v,n;}e[maxm];
int s,t;
int h[maxn],te;
int n,m,ta,tb,tc;
int lay[maxn];
void ae(int s,int t,int v)
{
e[te].t=t;e[te].v=v;e[te].n=h[s];h[s]=te++;
}
bool build()
{
int u,v,c;
memset(lay,-1,sizeof(lay));
queue<int>Q;
Q.push(s);lay[s]=0;
while (!Q.empty())
{
u=Q.front();Q.pop();
for (c=h[u];~c;c=e[c].n)
{
if (e[c].v&&lay[e[c].t]==-1)
{
lay[e[c].t]=lay[u]+1;
Q.push(e[c].t);
}
}
}
return lay[t]!=-1;
}
int find(int u,int low)
{
int tans,ans=0,p,k;
if (u==t)
return low;
for (p=h[u];(~p)&&low;p=e[p].n)
{
if (lay[e[p].t]==lay[u]+1&&(tans=find(e[p].t,min(low,e[p].v))))
{
e[p].v-=tans;
e[p^1].v+=tans;
ans+=tans;low-=tans;
}
}
return ans;
}
int dinic()
{
int ans=0,tans;
while (build())
while (tans=find(s,1e9+7))
ans+=tans;
return ans;
}
int main()
{
memset(h,-1,sizeof(h));
scanf("%d%d",&n,&m);
s=0;t=n+1;
for (int i=1;i<=n;i++)
{
scanf("%d%d",&ta,&tb);
ae(s,i,ta);ae(i,s,0);
ae(i,t,tb);ae(t,i,0);
}
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&ta,&tb,&tc);
ae(ta,tb,tc);
ae(tb,ta,tc);
}
printf("%d\n",dinic());
return 0;
}