吐槽&记录 突然才知道自己太菜了，今天t1又因为输出的时候少输出了一个换行符报零，加上就A，真伤心…linux换行和空格是一个意思啊…t3正解过了
Michael为救哥哥身陷囹圄，被关进foxriver监狱。为准备越狱，他需要散布消息给监狱中其他人来共同协作，但是监狱中鱼龙混杂，分成各个小团体，内部消息传递单向传输。问题1：初始至少需要向多少个透漏消息，使得监狱内所有人都获知消息。 问题2，至少需要添加几条传输线路(边)，使任意向一个人散步消息后，经过若干次传送，监狱内所有的人最终都能得到消息。
从文件break.in中输入数据。 输入的第一行包含一个整数 N：监狱人数（2 <= N <= 100）。用前 N 个正整数标识每个人。接下来 N 行中每行都表示一个消息传递列表（分发列表）。第 i+1 行包括 i 的接收消息的人的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
输出到文件break.out中。 输出的第一行包含一个正整数：问题1的解。第二行应该包含问题2的解。
5 2 4 3 0 4 5 0 0 0 1 0
1 2
2A代码…显然tarjan一下然后统计出入度就可以了
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #define MAXN 100+10 using namespace std; vector<int>G[MAXN]; int timer,N,viss[MAXN],dfnn[MAXN],loww[MAXN],stackk[MAXN],t[MAXN],topp,innn[MAXN],outtt[MAXN],cnt,ccc; void tarjan(int x){ viss[x]=true;//viss表示在栈中 stackk[++topp]=x; dfnn[x]=++timer; loww[x]=timer; int size=G[x].size(); for(register int i=0;i<size;i++){ int v=G[x][i]; if(!dfnn[v]){//如果v没有走过 tarjan(v); loww[x]=min(loww[x],loww[v]); }else{ if(viss[v]){//在栈中,则用其dfnn值来更新x loww[x]=min(loww[x],dfnn[v]); } } } if(loww[x]==dfnn[x]){ viss[x]=false; cnt++; t[x]=cnt; while(stackk[topp]!=x){ viss[stackk[topp]]=false; t[stackk[topp]]=cnt; topp--; } topp--; } } int main(){ freopen("break.in","r",stdin); freopen("break.out","w",stdout); scanf("%d",&N); for(register int i=1;i<=N;i++){ int tempp; while(scanf("%d",&tempp)&&tempp){ if(tempp!=i) G[i].push_back(tempp); } } for(register int i=1;i<=N;i++){ if(!dfnn[i]) tarjan(i);//找出强连通分量之后 ccc++; } if(ccc==1){ printf("1\n0\n"); return 0; } for(register int i=1;i<=N;i++){ int size=G[i].size(); for(register int j=0;j<size;j++){ int v=G[i][j]; if(t[i]!=t[v]){ outtt[t[i]]++; innn[t[v]]++; } } } int innh=0,outth=0; for(register int i=1;i<=cnt;i++){ if(innn[i]==0) innh++; if(outtt[i]==0) outth++; } printf("%d\n",innh); int maxn=max(innh,outth); printf("%d\n",maxn); return 0; }用的不是linux，自认倒霉
又到了新高一年级文理分科的时候了，每年的这个时候都比较伤感，因为有的要离开到其他班，有的新加入班级。负责安排座位的大川同学制定了这样的计划： 比如A和B都是本班学生且是好朋友，A分到了其他班，而C则是外班进入这个班的，C和A并不熟悉，而C和B关系很好，那么小x为了照顾A和C的情绪，就会让B坐在A的位置，C坐在B的位置。每个学生都只愿意坐到自己好朋友的座位或自己原来的座位。 当然，实际情况可能很复杂，比如一个班里的同学之间关系不一定好，外班进来的可能和本班很多人关系都很好。 现在告诉你，和大川所在班有关系的人一共有n个人，大川想知道有没有一个合理的方案来满足自己的座位安排计划。
从文件class.in中输入数据。 本题为多组数据，第一行一个整数M，表示有M组测试数据。 对于每组测试数据，每组的第一行一个整数n，表示一共有n个人和这个班有关系。 接下来一行n个整数，第i个整数表示第i个人是否是本班学生（0表示不是，1表示是，分到其他班的也算是本班学生） 接下来一行n个整数，第i个整数表示第i个人是否要分到其他班（0表示留在本班，1表示分到其他班，如果第i个人是由外班分进来的，那么第i个整数就是一个随机整数，没有实际意义） 接下来是一个n行n列的一个二维矩阵，第i行第j列的数表示第i个人和第j个人是否关系很好（1表示认识，0表示0 认识），对角线上是0，自己一定认识自己
输出到文件class.out中。 每组数据，如果存在一个方案，输出 “ˆ_ˆ”(不含引号)。 如果没有方案，输出 “T_T”(不含引号)。都是半角字符。
1 3 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0
ˆ_ˆ
对于 30% 的数据满足 1 ≤ n ≤ 12。 对于 100% 的数据满足 1 ≤ n ≤ 50,1 ≤ T ≤ 20。 1A代码，二分图匈牙利跑得飞快
#include<iostream> #include<cstring> #include<cstdio> #include<vector> #define MAXN 300+10 using namespace std; int M,n; int a[MAXN],b[MAXN],G[MAXN][MAXN],girl[MAXN]; bool visit[MAXN]; bool find(int x){ if(visit[x]) return false; for(int i=1;i<=n;i++){ if(G[x][i]&&(!visit[i])){ visit[i]=true; if(girl[i]==-1||find(girl[i])){//还没有男友或者虽然名花有主但是可以给主再找个女友 girl[i]=x; return true; } } } return false; } int main(){ freopen("class.in","r",stdin); freopen("class.out","w",stdout); scanf("%d",&M); while(M--){ scanf("%d",&n); for(register int i=1;i<=n;i++){//1是本班 scanf("%d",&a[i]); } for(register int i=1;i<=n;i++)scanf("%d",&b[i]);//1为到其他班,0为留在本班,其他表示是其他班分进来的 for(register int i=1;i<=n;i++){ for(register int j=1;j<=n;j++){ scanf("%d",&G[i][j]); if(G[i][j]==1&&a[i]==1&&a[j]==0) G[i][j]=0;//不连向外班异班的j无论转不转来,本班的i不转,所以本班不连外班,外班可以连本班 if(G[i][j]==1&&a[i]==1&&b[i]==1) G[i][j]=0; //本班转到外班,所有他到别人的关系均断 if(G[i][j]==1&&a[i]==0&&(b[i]==0||b[i]==1)) G[i][j]=0; //是异班,不转到本班,与本班的关系断 if(G[i][j]==1&&a[i]==0&&a[j]==0&&b[i]!=0&&b[i]!=1) G[i][j]=0;//转到本班,与原来的朋友断交 } } for(register int i=1;i<=n;i++){ G[i][i]=1; if(a[i]==1&&b[i]==1)G[i][i]=0; if(a[i]==0&&b[i]!=0&&b[i]!=1)G[i][i]=0; } bool judge=true; memset(girl,-1,sizeof(girl)); for(int i=1;i<=n;i++){ if(a[i]==1&&b[i]==1)continue; if(a[i]==0&&(b[i]==0||b[i]==1)) continue; memset(visit,false,sizeof(visit)); if(!find(i)){ judge=false; break; } } if(judge) printf("^.^\n"); else printf("T.T\n"); } return 0; }