做国际网站每年要多少钱,企业网站做口碑营销,海洋生态文明建设的网站名,网站建站公司费用解析
很好的题 也就是我没做出来的意思 反向思维似乎是我欠缺的 这道题也是 也许做题时应该多特意往这边想想 当正向看并没有太好的性质时#xff0c;也许反过来能使题目豁然开朗
容易想到暴力n方如何做 #xff08;以下均指反图#xff09; 找到1所在的点#xff0c;染色…解析
很好的题 也就是我没做出来的意思 反向思维似乎是我欠缺的 这道题也是 也许做题时应该多特意往这边想想 当正向看并没有太好的性质时也许反过来能使题目豁然开朗
容易想到暴力n方如何做 以下均指反图 找到1所在的点染色找到其导出的子图在其中再找到最小的点再求导出图…直到子图大小为1时把结点放到当前答案序列的开头
那么不难发现每个点导出的子图都是占据答案序列上连续的一段同时最小的结点会在这一段的最后
然后…我就发现不出来了…
考虑反过来想 答案序列最后一个点必然是入度为0的编号最大的点 因为它永远不会被其他点的导出子图选中并且会被贪心的在全部图中最后一个选到 而且去掉这个点和相关的边后剩下的图依然满足这个性质 所以就得到了本题的策略在反图上跑字典序最大的拓扑即可 代码实现上把队列改称大根堆即可
代码
#includebits/stdc.hconst int N1e5100;
const int M2e3100;
const int mod1e97;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
inline ll read() {ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}const int key13331;int n,m,Q;
struct node{int to,nxt;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;return;
}
int du[N],ans[N],num;
priority_queueintq;void init(){memset(fi,-1,sizeof(fi));cnt-1;memset(du,0,sizeof(du));num0;
}
int main(){
#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);
#endifint Tread();while(T--){init();nread();mread();for(int i1;im;i){int xread(),yread();addline(y,x);du[x];}for(int i1;in;i){if(!du[i]) q.push(i);}while(!q.empty()){int nowq.top();q.pop();ans[num]now;for(int ifi[now];~i;ip[i].nxt){int top[i].to;if(--du[to]0){q.push(to);}}}if(num!n) printf(Impossible!\n);else{for(int in;i1;i--) printf(%d ,ans[i]);putchar(\n);}}return 0;
}
/*5 37 1 4 1 9 1 3 5 31 1 4 22 3 5
*/
