Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 蜜汁TLE求指点（HLPP）

Posted by X_o_r3 at 2018-02-24 16:19:18 on Problem 3436 and last updated at 2018-02-24 16:20:16
```/*如果在输出前加一个 return 0;
那么就不会TLE了（显然会WA）*/
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=105,maxe=5305,INF=0x3f3f3f3f;
int N,P,M,St,Ed,cnt,que[maxn],lnk[maxn],nxt[maxe],son[maxe],cap[maxe],gap[maxe],H[maxn],tot=1,Ans[maxn],len,mf[maxn],Pin[maxn][11],Pout[maxn][11];
int ZERO[11],FULL[11]={1,1,1,1,1,1,1,1,1,1,1};
bool vis[maxn],G[maxn][maxn];
int x,h;
inline int operator < (const Ad &c) const{
return h<c.h;
}
}Hep[maxe];
struct Print_{
int x,y,w;
}C[maxe];
inline void Put(int x,int h){
}
pop_heap(Hep+1,Hep+1+len);
return Hep[len--];
}
inline void Add(int x,int y,int tf,int fo=0){
nxt[++tot]=lnk[x],son[lnk[x]=tot]=y,cap[tot]=tf-fo;
nxt[++tot]=lnk[y],son[lnk[y]=tot]=x,cap[tot]=fo;
}
char ch=getchar();
for (Res=0;!isdigit(ch);ch=getchar());
for (;isdigit(ch);ch=getchar()) Res=(Res<<3)+(Res<<1)+ch-48;
}
inline void Gap(int val){
for (int i=N;i;--i)
if ((i^St)&&(i^Ed)&&H[i]>val&&H[i]<=N) H[i]=N+1;
}
inline int Push(int x,int y,int id){
int w=min(Ans[x],cap[id]);
if (!w) return 0;
cap[id]-=w,cap[id^1]+=w,Ans[x]-=w,Ans[y]+=w;
return w;
}
inline int HLPP(){
len=0,memset(Ans,0,sizeof Ans),memset(H,0,sizeof H),Ans[St]=INF,Put(St,H[St]=N); int K;
while (len){
K=Get().x;
if (!Ans[K]) continue;
for (int j=lnk[K];j;j=nxt[j])
if ((K==St||H[son[j]]+1==H[K])&&Push(K,son[j],j)&&(son[j]^St)&&(son[j]^Ed))
Put(son[j],H[son[j]]);
if ((K^St)&&(K^Ed)&&Ans[K]){
if (!--gap[H[K]]) Gap(H[K]);
++gap[++H[K]],Put(K,H[K]);
}
}
return Ans[Ed];
}
inline int check(int A[11],int B[11]){
for (int k=0;k<P;++k) if (A[k]+B[k]==1) return 0;
return 1;
}
int main(){
freopen("data.in","r",stdin),freopen("data.out","w",stdout);
for (int k=1;k<=M;++k){
}
for (int i=M;i;--i)
for (int j=M;j;--j) if (i!=j&&(G[i][j]=check(Pout[i],Pin[j]))) Add(i+M,j,mf[j]);
printf("%d ",HLPP());
for (int i=2*M;i>M;--i)
for (int j=lnk[i];j;j=nxt[j]) if (!(j&1)&&son[j]<=M&&cap[j^1]>0) C[++cnt]=(Print_){i-M,son[j],cap[j^1]};
printf("%d\n",cnt);
/*如果在这里加一个 return 0;
那么就不会TLE了（显然会WA）*/
for (int i=cnt;i;--i) printf("%d %d %d\n",C[i].x,C[i].y,C[i].w);
return 0;
}```

Followed by: