T1

 裸的拓扑排序

1 #include 
     
       2 #include 
      
        3 struct E{ 4     int next,to; 5 }e[100001]; 6 int n,m,t,a,b,sz,pd,head[100001],reg[100001],in[100001]; 7 void insert(int a,int b) 8 { 9     sz++;10     e[sz].next=head[a];11     head[a]=sz;12     e[sz].to=b;13 }14 int dfs(int x)15 {16     reg[x]=1;in[x]=1;17     for (int i=head[x];i;i=e[i].next)18     {19         if (in[e[i].to])20         {21             pd=0;22             return 1;23         }24         else25         {26             if (!reg[e[i].to]&&dfs(e[i].to)) return 1;27         }28     }29     in[x]=0;30     return 0;31 }32 int main()33 {34     scanf("%d",&t);35     while(t--)36     {37         memset(head,0,sizeof(head));38         memset(reg,0,sizeof(reg));39         memset(in,0,sizeof(in));40         sz=0;pd=1;41         scanf("%d%d",&n,&m);42         for (int i=1;i<=m;i++)43         {44             scanf("%d%d",&a,&b);45             insert(a,b);46         }47         for (int i=1;i<=n;i++) if (pd&&!reg[i]) dfs(i);48         printf("%d\n",pd);49     }50 }
      
     

 

T2

 略微改编的最短路

1 #include 
     
       2 #include 
      
        3 int t,n,m[101][101],f[101],in[101]; 4 char x; 5 void dfs(int x) 6 { 7     int cnt=0; 8     for (int i=1;i<=n;i++) 9     {10         if (m[x][i]==1)11         {12             if (f[i]==-1||f[x]+cnt
      
     

 

T3

题目描述：

有一个魔术师，他有 n 个未知整数，每个数是 0 或者 1，你的目的是猜出魔术师的这 n 个未 知数。

为了猜出 n 个未知数，你可以向魔术师询问第 x 到第 y 个数的异或和，但是每次询问你都需 要给魔术师一定的金钱，不同的询问需要不同的金钱。

你现在需要计算出猜出这 n 个数至少需要花费多少钱。

 一道略有难度的MST

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 struct E{ 5     int a,b,w; 6 }e[1000001]; 7 int n,w,sz=0,ans=0,cnt=0,f[1001]; 8 bool cmp(E a,E b) {
   return a.w