[网络流24题]最长k可重区间集

// q.c#include
#include
#include
#include
#include
#include
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int M&＃61;500&＃43;5,INF&＃61;(int)1e8;
struct Edge {int u,v,nex,cost,flow,cap; Edge() {}Edge(int a,int b,int c,int d,int e,int f):u(a),v(b),nex(c),cost(d),flow(e),cap(f) {}
}ed[M<<3];
int cnt,head[M<<1];
void add_edge(int a,int b,int c,int d) {ed[cnt]&＃61;Edge(a,b,head[a], c,0,d); head[a]&＃61;cnt&＃43;&＃43;;ed[cnt]&＃61;Edge(b,a,head[b],-c,0,0); head[b]&＃61;cnt&＃43;&＃43;;
}
struct Dinic {int n,s,t,dis[M<<1],pre[M<<1],lim[M<<1]; bool in[M<<1]; queue Q;Dinic():n(0),s(0),t(0) {mem(dis); mem(pre); mem(lim); mem(in);while(!Q.empty()) Q.pop();}bool spfa(int &Flow,int &Cost) {for(int i&＃61;0;i<&＃61;n;i&＃43;&＃43;) dis[i]&＃61;lim[i]&＃61;INF,pre[i]&＃61;in[i]&＃61;0;dis[s]&＃61;0; in[s]&＃61;true; Q.push(s);int u,i; Edge e;while(!Q.empty()) {u&＃61;Q.front(); Q.pop(); in[u]&＃61;false;for(i&＃61;head[u];i!&＃61;-1;i&＃61;ed[i].nex) {e&＃61;ed[i];if(dis[u]&＃43;e.coste.flow) {dis[e.v]&＃61;dis[u]&＃43;e.cost; pre[e.v]&＃61;i;lim[e.v]&＃61;min(lim[u],e.cap-e.flow);if(!in[e.v]) in[e.v]&＃61;true,Q.push(e.v);}}}if(dis[t]&＃61;&＃61;INF) return false;Flow&＃43;&＃61;lim[t];Cost&＃43;&＃61;lim[t]*dis[t];u&＃61;t;while(u!&＃61;s) {i&＃61;pre[u]; ed[i].flow&＃43;&＃61;lim[t];ed[i^1].flow-&＃61;lim[t]; u&＃61;ed[i].u;}return true;}int solve(int x,int y,int z) {s&＃61;x; t&＃61;y; n&＃61;z;int Flow&＃61;0,Cost&＃61;0;for(;spfa(Flow,Cost););return Cost;}
}DC;
struct Data {int x,y,z;bool operator <(const Data &A) const {if(x!&＃61;A.x) return x}da[M],tmp[M<<1];
int ref[M<<1];
int main() {freopen("interv.in","r",stdin);freopen("interv.out","w",stdout);memset(head,-1,sizeof(head));int n,k,m&＃61;0,a,b,p,q,tot&＃61;0;scanf("%d%d",&n,&k);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) {scanf("%d%d",&a,&b);if(a>&＃61;b) continue;&＃43;&＃43;m;q&＃61;m<<1; p&＃61;q-1;da[m].x&＃61;p,da[m].y&＃61;q;da[m].z&＃61;b-a;tmp[p].x&＃61;a,tmp[p].y&＃61;p;tmp[q].x&＃61;b,tmp[q].y&＃61;q;}sort(tmp&＃43;1,tmp&＃43;(m<<1)&＃43;1);for(int i&＃61;1;i<&＃61;(m<<1);i&＃43;&＃43;) {if(tmp[i].x!&＃61;tmp[i-1].x) ref[tmp[i].y]&＃61;&＃43;&＃43;tot;else ref[tmp[i].y]&＃61;tot;}for(int i&＃61;1;i<&＃61;m;i&＃43;&＃43;) {da[i].x&＃61;ref[da[i].x];da[i].y&＃61;ref[da[i].y];add_edge(da[i].x,da[i].y,-(da[i].z),1);}for(int i&＃61;1;i}