首页 > 代码库 > UOJ #56. 【WC2014】非确定机
UOJ #56. 【WC2014】非确定机
题意大意：给出一个输出文件，求输入。
1.满足所求的输入文件是一张图，n个点，m条边，所用算法是k（k在给出的输出文件中给出了）
2.算法是图论算法？!k基本上→两位数组成，若十位数相同，说明基本算法可能是相同的。
3.给出一个可执行文件，可以在终端中运行自己造出的数据，从而猜测算法。
4.你所给出的图不能有重边，但可以有自环，边权<=2*10^4
5.p是在给出的输出文件中给定的一个参数，这个参数由你所造出的图由某种计算方式所决定的。
先挖坑。。。感觉是一个很有意思的构造+XJB乱搞题，假设是WC的话，我能搞2个半个小时提答，那么。。。。。
闷声滚大粗
(1)喜闻乐见的01矩阵，再加上样例的那个例子，就是A(i,j)表示是否有i向j连边的意思。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m;13 int main()14 {15 yyj("nm1");16 cin>>n;17 llg tot=0;18 for (llg i=1;i<=n;i++)19 for (llg j=1;j<=n;j++)20 {21 llg x;22 //tot++;23 cin>>x;24 if (x) tot++;25 if (x) cout<<i<<" "<<j<<" 1"<<endl;26 }27 cout<<tot;28 return 0;29 }
(2)算法编号k=10，新的图论算法，随便自己造个图用给出的程序试一试发现就是以1为原点的单源最短路，p就是边的数目。
考虑如何构造：
1.显然一号点向每个点连一条所要求的权值的边就满足了最短路的条件，但是边数只有n-1条，即p‘!=p,可以get 4分。
2.按照上面的做法打完拿了程序一测正确性发现GG，我之前没看到边权<=2*10^4，好吧，按照所要求的最短路长度排序，按照从小到达的顺序处理，如果小于2*10^4直接和一号点相连，不然找到之前的处理过的点，而且当前点要求的权值减去处理过的点的权值小于等于2*10^4中权值最小的那一个连边，考虑到p的限制，在已经处理过的最小权值的可连边的点之后的点再向待处理的点连出的边将不对答案产生影响。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,p,k;13 bool d[maxn][maxn];14 15 struct node16 {17 llg p,val;18 }a[maxn];19 bool cmp(const node&a,const node&b) {return a.val<b.val;}20 int main()21 {22 yyj("nm2");23 cin>>n>>k>>p;24 for (llg i=1;i<=n;i++)25 {26 a[i].p=i;27 cin>>a[i].val;28 }29 sort(a+1,a+n+1,cmp);30 p-=n;31 p++;32 for (llg i=2;i<=n;i++)33 {34 llg j;35 for (j=1;j<i;j++) 36 if (a[i].val-a[j].val<=20000) 37 {38 cout<<a[j].p<<" "<<a[i].p<<" "<<a[i].val-a[j].val<<endl;39 break;40 }41 j++;42 while (p>0 && j<i)43 {44 p--;45 cout<<a[j].p<<" "<<a[i].p<<" "<<20000<<endl;46 j++;47 }48 }49 return 0;50 }
(3)算法编号k=11，嗯，类似于最短路，但是这个点还是要多试试，一开始我认为是求到每个点的不同路径的最短路的数目，我靠不会构啊，再去试了几组数据之后发现：
所求为所有点之间的最短路，但是和边权没有关系，即边权默认为1，p为边数。
沉思。。。。。没办法了打一个暴力，想到优化显然矩阵中为1点的相当于所对应的(x,y)一定连了一条边。再一看有400个1。p也是400，在想想这很显然啊，连出了所有为1的边之后答案就确定了。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1001010 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,p,k;13 bool d[maxn][maxn];14 15 struct node16 {17 llg p,val;18 }a[maxn];19 bool cmp(const node&a,const node&b) {return a.val<b.val;}20 int main()21 {22 yyj("nm3");23 cin>>n>>k>>p;24 cout<<n<<" "<<p<<" "<<k<<endl;25 for (llg i=1;i<=n;i++)26 {27 for (llg j=1;j<=n;j++)28 {29 llg x;30 cin>>x;31 if (x==1) cout<<i<<" "<<j<<" 2333"<<endl;32 }33 }34 return 0;35 }
(4)
(5)
(6)
(7)
(8)
(9)
(10)
UOJ #56. 【WC2014】非确定机