Time Limit: 2000MS | Memory Limit: 65536K | |
Total Submissions: 22553 | Accepted: 8530 |
Description
Input
Output
Sample Input
5 3 7 3 8 10 3 6 8 1 1 3 1 10 11 1
Sample Output
6
题意:给定N个区间[ai,bi],对应ci,求一个集合,对每个区间都有ci个数在集合中,求集合的数的最小个数
思路:差分约束,s(bi)-s(ai-1)>=ci,s(i+1)-s(i)>=0,s(i)-s(i+1)>=-1。以区间最左端的Min为源点,求最长路
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> using namespace std; const int maxn=50010; const int INF=(1<<29); int N; int a,b,c; struct Edge { int v,w; Edge *next; };Edge e[maxn*10]; bool vis[maxn]; int cnt[maxn]; int dist[maxn]; int Min,Max;///Min作为源点 void add_edge(int u,int v,int w) { Edge *pre=&e[u]; Edge *p=(Edge*)malloc(sizeof(Edge)); p->v=v;p->w=w; p->next=pre->next; pre->next=p; } bool relax(int u,int v,int w) { if(dist[u]+w>dist[v]){ dist[v]=dist[u]+w; return true; } return false; } bool spfa() { for(int i=Min;i<=Max+1;i++) dist[i]=-INF; dist[Min]=0; memset(vis,0,sizeof(vis)); memset(cnt,0,sizeof(cnt)); queue<int> q; q.push(Min);vis[Min]=1;cnt[Min]++; while(!q.empty()){ int u=q.front();q.pop();vis[u]=0; for(Edge *p=e[u].next;p!=NULL;p=p->next){ int v=p->v,w=p->w; if(relax(u,v,w)){ if(!vis[v]){ q.push(v); vis[v]=1; cnt[v]++; if(cnt[v]>N) return false; } } } } return true; } int main() { while(cin>>N){ memset(e,0,sizeof(e)); Min=INF;Max=-INF; for(int i=0;i<N;i++){ scanf("%d%d%d",&a,&b,&c); add_edge(a,b+1,c); if(a<Min) Min=a; if(b>Max) Max=b; } for(int i=Min;i<=Max;i++){ add_edge(i,i+1,0); add_edge(i+1,i,-1); } spfa(); cout<<dist[Max+1]<<endl; } return 0; }
原文:http://www.cnblogs.com/--560/p/4412348.html