T1菜肴制作：拓扑排序+大根堆
卡了好一会儿才过掉 。正序拓扑的话贪心策略会出错 。
保证先输出小的 ， 倒序拓扑保证先搞大的 。然后插到大根堆里 。
每次取出最大的（堆顶）进行拓扑扩展 。pop出来的直接扔进栈里 。
多判有点恶心 。记得清空（我就因为tot没清空 ， 样例第三组单测正确 ， 多测就错 。。）
还有一个特殊判断：栈内元素个数与本身元素个数是否相符 。
不相符就是剩下了环搞不出来 ， 就行了 。
#include#include#include#include#include#include#define rint register intusing namespace std;int T,n,m,a,b,tot,first[100003];int du[100003];struct node{int u,v,nxt;};bool pan=0,vis[100003];inline void add(int uu,int vv,node edge[]){++tot;edge[tot].u=uu;edge[tot].v=vv;edge[tot].nxt=first[uu];first[uu]=tot;}int main(){scanf("%d",&T);while(T--){scanf("%d %d",&n,&m);memset(vis,0,sizeof(vis));memset(du,0,sizeof(du));memset(first,0,sizeof(first));tot=0;priority_queue q;stack s;node edge[100003];for(rint i=1;i<=m;++i){scanf("%d %d",&a,&b);add(b,a,edge);du[a]++;}for(rint i=1;i<=n;++i){if(!du[i])q.push(i);vis[i]=1;}if(q.empty()){cout<<"Impossible!"<
View Code
T2矩阵游戏：二分图
锝瑟一把这题全hzoj我是第一个A掉的
二分图 ， 一开始还真没想起来 。查bzoj上这道题的时候撇了一眼看到了二分图三个字 。
好的 。（不要脸）但是真的忘了啊QAQ只好翻出ftp里尘封多年的二分图ppt 。
手码了一遍匈牙利感觉还不错 。
挺基础 ， 行列分别建点 ， 黑格建边 ， 跑一边匈牙利 ， 用黑格去匹配行和列 。
然而没认真看题 ， 人家让输出“Yes”或“No” ， 我输出“YES”“NO”完美w0 。。。
加了一堆卡常特盘 ， 148毫算是挺快的了吧？（wtf 102ms！收小的一拜）
#include#include#include#include#include#includeusing namespace std;const int N=205;int a[N][N];int vis[N],matx[N],maty[N];int tot;int n;int hun(int x){for(int i=1;i<=n;i++){//int y=to[i];if(!vis[i]&&a[x][i]){vis[i]=1;if(maty[i]==-1||hun(maty[i])){maty[i]=x;matx[x]=i;return 1;}}}return 0;}int main(){int T;scanf("%d",&T);while(T--){tot=0;memset(maty,-1,sizeof(maty));memset(matx,-1,sizeof(matx));scanf("%d",&n);int cnt=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)scanf("%d",&a[i][j]);int ans=0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));if(hun(i)) ans++;}//cout
View Code
T3约会 ：基环树
为什么基环树的题目都这么恶心还是我太弱鸡了？
我可能卡了一年 。自己想出来的代码5.0k ， 198行……我真的没勇气调下去了 。
记录了一大堆东西 。判断的语句写了一堆 。。真的是堆QAQ 。
#include#include#include#include#include#include#define rint register intconst int L=1<<20|1;char buffer[L],*S,*T;#define getchar() ((S==T&&(T=(S=buffer)+fread(buffer,1,L,stdin),S==T))?EOF:*S++)using namespace std;int n,m,head[500005],tot,fat[500005];int dex,cnt,t,bar[500005],bl[500005],ac[500005];int d[500005],f[500005][20],l_a[500005],l_b[500005];vectordell[500005];queueq;struct node{int to,nxt;}edge[500005];int read(){rint a=0,b=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')b=-1;ch=getchar();}while(ch>='0'&&ch
