幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。
经典题目;
值得吐槽的是,数据里有一个10w个点的链,已被T成狗......
只有正向从n到1向起点连边才能过;
还有一种方法是最开始就把所有点放队列里;
通过率下降2个百分点;
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cstdlib> 6 #include<algorithm> 7 #include<ctime> 8 #include<cmath> 9 #include<queue> 10 #include<map> 11 #include<set> 12 using namespace std; 13 #define FILE "dealing" 14 #define LL long long 15 #define up(i,j,n) for(int i=j;i<=n;i++) 16 #define pii pair< int , int > 17 #define abs(x) (x)<0?-(x):(x) 18 namespace IO{ 19 char buf[1<<15],*fs,*ft; 20 int gc(){return fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft),fs==ft?-1:*fs++;} 21 int read(){ 22 int x=0,ch=gc(),f=0; 23 while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=gc();} 24 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();} 25 return f?-x:x; 26 } 27 }using namespace IO; 28 bool chkmin(int &a,int b){return a>b?a=b,true:false;} 29 bool chkmax(int &a,int b){return a<b?a=b,true:false;} 30 const int maxn(1000500),inf(100000000); 31 int n,m,s; 32 struct node{ 33 int y,next,v; 34 }e[maxn<<2]; 35 int linkk[maxn],len=0; 36 void insert(int x,int y,int v){ 37 e[++len].y=y; 38 e[len].next=linkk[x]; 39 linkk[x]=len; 40 e[len].v=v; 41 } 42 int q[maxn+10],tail=0,head=0,d[maxn],t[maxn]; 43 void print(){printf("-1 ");exit(0);} 44 bool vis[maxn]; 45 int main(){ 46 freopen(FILE".in","r",stdin); 47 freopen(FILE".out","w",stdout); 48 n=read(),m=read();int x,A,B;s=0; 49 50 up(i,1,m){ 51 x=read(),B=read(),A=read(); 52 if(x==1)insert(B,A,0),insert(A,B,0); 53 if(x==2){ 54 insert(B,A,1); 55 if(A==B)print(); 56 } 57 if(x==3)insert(A,B,0); 58 if(x==4){ 59 insert(A,B,1); 60 if(A==B)print(); 61 } 62 if(x==5)insert(B,A,0); 63 } 64 for(int i=1;i<=n;i++)insert(0,i,1); 65 up(i,0,n)q[++tail]=i,d[i]=-inf,t[i]++,vis[i]=1; 66 //关键中的关键 67 d[0]=0; 68 while(head!=tail){ 69 head++; 70 x=q[head]; 71 if(head==maxn-10)head=0; 72 for(int i=linkk[x];i;i=e[i].next){ 73 if(d[e[i].y]<d[x]+e[i].v){ 74 d[e[i].y]=d[x]+e[i].v; 75 if(!vis[e[i].y]){ 76 vis[e[i].y]=1; 77 q[++tail]=e[i].y; 78 t[e[i].y]++; 79 if(t[e[i].y]==n)print(); 80 if(tail==maxn-10)tail=0; 81 } 82 } 83 } 84 vis[x]=0; 85 } 86 LL ans=0; 87 for(int i=1;i<=n;i++)ans+=d[i]; 88 printf("%lld ",ans); 89 return 0; 90 }