暑假Q去了趟q州实习(fn)Q回来后到学校开始省赛的集训。从八月十日号到现在Q我在不分白天黑夜的敲题Q学法。《算法导论》已被我借了快一q了?
一路走来，感慨颇多Q有心酸Q也有快乐?/span>
有时?x)因为提交一个题目，从早上一直WA
省赛之前Q学校还有几个队员有的时候交一下，而现在就只有我的伙伴也只有百度和h?
省赛Q早已预见的l果Q我要的只是的进步?
见识q很多牛人，学习(fn)了很多的法Q也敲过上万行的代码?
在湖大的|站上敲?50
在算法的h里，我这小的蜗牛，也只有一天一天的努力往上爬Q不知道何时才能看到那些灿烂的阳光?
也许Q阳光早已洒落在q程里了?
有时候会(x)惻I如果我早一Ҏ(gu)触ACM,
可是生活没有如果Q刚开始相恋，我就要毕业了?
有些遗憾Q但也不(zhn)，在我有生之年Qؓ(f)之奋斗过?
?nbsp; 生活
很少M课，估计每节译և勤的同学不会(x)过两位数?
但我很珍惜这D|后的学校生活Q可以舒服的睡觉Q可以自q敲题Q可以轻杄写字Q可以不那些关于经危带来的׃危机Q可以放肆的像个孩子?
臛_在没有毕业之前我q是一个学生，但很快就不是了?
走入C会(x)Q工作，我就要承担v一份责M。亲q爸爸妈妈Qؓ(f)了我苦了大半辈子。我要努力挣钱，让我们的日子q的好点?
朋友们，q段联系了Q其实我也不惌栗?
天冷了，整天一个h对这?sh)脑Q有Ҏ(gu)回家了?
生活很简单，每天睡到?ji)点起床Q忙zM下卫生，开?sh)脑Q在北大的题?gu)里遨游了，无边无际?
中午Q匆忙的吃个快餐。杯咖啡，打开H帘Q晒?x)儿太阳Ql做题?
晚上的时候，跑到学校食堂吃顿饭。然后在夜幕下，一个h游荡?
我很喜欢L场，那些I旷与寂寥，是狂Ƣ过后一个h(zhn)伤。听着q播里《旋木》，王菲的空灵与Ua?
极目q眺Q北方的天空有两颗闪亮的星星Q不知道他们隔了有多q，有没有见证过所谓的永恒?
回来后，l箋敲题q午夜?
Z么我?x)来到这个星球上Qƈ且是q不来，晚不来，偏偏在这个时候来了呢Q?
在我没来到这个世界来之前的那么多q_(d)世界是个什么样子呢Q历史上那么多的人，他们都死了，到底他们有过怎样的生z？
是什么力量生了生命Q怎么有了我Q?太神奇了Q?wbr>
未来?x)变成什么样子呢Q一癑ֹQ一千年Q到时候我们都不在了?
一惛_我们都会(x)死，׃(x)很?zhn)伤，那些无可奈何的(zhn)伤?
以前从来惌的问题，随着L(fng)奶奶的去世，久久的会(x)在心里缠l着?
(zhn)伤Q是因ؓ(f)x着失去?
也许Q活着׃仅只是ؓ(f)了活着而活着Q一场游戏一场梦Q管那么多干嘛呢Q?nbsp;
有梦做Q有酒就醉，痛痛快快的在q个世界C遭吧?wbr>
妈妈的生日快CQ准备给她老h安一份礼物?
打算着再敲两个月题Q努力的向牛看齐Q不要那么菜p?
老姐l婚了，打算到北京去看看他们?
打算着明年毕业实习(fn)Q毕业设计，扑ַ作?
打算不要L疲劳战术了，得好好的ȝ一下n体?
打算调整好生物钟Q十二点以前一定上床睡觉?
打算着选个阛_灿烂的日子，好好的出去走走玩玩。这些天天气很好Q但一直舍不得Q时间很不够用?
打算好好的敲题，好好的学?fn)，好好的生z，好好的待生命中遇到的每一个h?
现在打算着马上关电(sh)脑上床睡觉?wbr>
]]>
//关键是在于区间篏计的时候一个偶数基数的问题
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{ int test,n,i,j;
int s[200],t[200],used[200];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&test);
while(test--)
{ scanf("%d",&n);
memset(used,0,sizeof(used));
for(i=0;i<n;i++)
scanf("%d%d",&s[i],&t[i]);
for(i=0;i<n;i++)
{ if(s[i]>t[i])
swap(s[i],t[i]);
if(s[i]%2==0)
s[i]--;
s[i]=s[i]/2;
if(t[i]%2==0)
t[i]--;
t[i]=t[i]/2;
for(j=s[i];j<=t[i];j++)
used[j]++;
}
sort(used,used+200);
printf("%d\n",used[199]*10);
}
return 0;
}
]]>
//最割定理是一个二分图中很重要的定理－Q－一个二分图中的最大匹配数{于q个图中的最点覆盖数?wbr>
//最点覆盖Q假如选了一个点q当于覆盖了以它ؓ(f)端点的所有边Q你需要选择最的Ҏ(gu)覆盖所有的?
#include<iostream>
using namespace std;
int n,m,res;
int l[500],r[500],map[500][500],used[500];
bool path(int u)
{int v;
for(v=0;v<n;v++)
if(map[u][v] && !used[v])
{used[v]=1;
if(r[v]==-1 || path(r[v]))
{ l[u]=v;
r[v]=u;
return true;
}
}
return false;
}
void solve()
{ int i;
memset(l,-1,sizeof(l));
memset(r,-1,sizeof(r));
for(i=0;i<n;i++)
if(l[i]==-1)
{ memset(used,0,sizeof(used));
if(path(i))
res++;
}
}
int main()
{ int i,a,b;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d%d",&n,&m))!=EOF)
{ memset(map,0,sizeof(map));
for(i=0;i<m;i++)
{ scanf("%d%d",&a,&b);
map[a-1][b-1]=1;
}
res=0;
solve();
cout<<res<<endl;
}
return 0;
}
]]>
//特点不需要徏模，原理q是朴素最大流原理Q寻扑֢q\径用DFS,如找C条增q\径，沿\边取?wbr>
#include<iostream>
using namespace std;
int n,m,res;
int l[300],r[300],map[300][300],used[300];
bool path(int u)
{int v;
for(v=0;v<m;v++)
if(map[u][v] && !used[v])
{used[v]=1;
if(r[v]==-1 || path(r[v]))
{ l[u]=v;
r[v]=u;
return true;
}
}
return false;
}
void solve()
{ int i;
memset(l,-1,sizeof(l));
memset(r,-1,sizeof(r));
for(i=0;i<n;i++)
if(l[i]==-1)
{ memset(used,0,sizeof(used));
if(path(i))
res++;
}
}
int main()
{ int Case,i,j,k,temp;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&Case);
while(Case--)
{ memset(map,0,sizeof(map));
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
{ scanf("%d",&k);
for(j=0;j<k;j++)
{scanf("%d",&temp);
map[i][temp-1]=1;
}
}
res=0;
solve();
if(res==n)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
什么是二分图，什么是二分囄最大匹配，q些定义我就不讲了，|上随便都找得到。二分图的最大匹配有两种求法Q第一U是最大流Q我在此假设读者已有网l流的知识）Q第二种是我现在要讲的匈牙利算法。这个算法说白了是最大流的算法，但是它跟据二分图匚wq个问题的特点，把最大流法做了化，提高了效率。匈牙利法其实很简单，但是|上搜不C么说得清楚的文章。所以我军_要写一下?br>最大流法的核心问题就是找增广路径Qaugment pathQ。匈牙利法也不例外Q它的基本模式就是：(x)
可见和最大流法是一L(fng)。但是这里的增广路径有它一定的Ҏ(gu)性，下面我来分析一下?br>Q注Q匈牙利法虽然Ҏ(gu)上是最大流法Q但是它不需要徏|络模型Q所以图中不再需要源点和汇点Q仅仅是一个二分图。每条边也不需要有方向。）
?是我l出的二分图中的一个匹配：(x)Q?Q?Q和Q?Q?Q。图2是在这个匹配的基础上找到的一条增q\径：(x)3->6->2->5->1->4?wbr>
(1)有奇数条辏V?br>(2)L(fng)在二分图的左半边Q终点在叛_辏V?br>(3)路径上的点一定是一个在左半边，一个在叛_边，交替出现。（其实二分囄性质决定了q一点，因ؓ(f)二分囑一边的点之间没有边相连Q不要忘记哦。）
(4)整条路径上没有重复的炏V?br>(5)L(fng)和终炚w是目前还没有配对的点Q而其它所有点都是已经配好对的。（如图1、图2所C，Q?Q?Q和Q?Q?Q在?中是两对已经配好对的点；而v?和终?目前q没有与其它炚w寏V）
(6)路径上的所有第奇数条边都不在原匚w中，所有第偶数条边都出现在原匹配中。（如图1、图2所C，原有的匹配是Q?Q?Q和Q?Q?Q，q两条配匹的边在?l出的增q\径中分边是第2和第4条边。而增q\径的W???条边都没有出现在?l出的匹配中。）
(7)最后，也是最重要的一条，把增q\径上的所有第奇数条边加入到原匚w中去Qƈ把增q\径中的所有第偶数条边从原匚w中删除（q个操作UCؓ(f)增广路径?wbr>取反
不难想通，在最初始Ӟq没有Q何匹配时Q图1中的两条灰色的边本n也是增广路径。因此在q张二分图中L最大配匹的q程可能如下Q?br>
(1)扑ֈ增广路径1->5Q把它取反，则匹配数增加??br>(2)扑ֈ增广路径2->6Q把它取反，则匹配数增加??br>(3)扑ֈ增广路径3->6->2->5->1->4Q把它取反，则匹配数增加??br>(4)再也找不到增q\径，l束?br>
当然Q这只是一U可能的程。也可能有别的找增广路径的顺序，或者找C同的增广路径Q最l的匚wҎ(gu)也可能不一栗但是最大匹配数一定都是相同的?br>
对于增广路径q可以用一个递归的方法来描述。这个描qC一定最准确Q但是它揭示了寻扑֢q\径的一般方法：(x)
“从点A出发的增q\?#8221;一定首先连向一个在原匹配中没有与点A配对的点B。如果点B在原匚w中没有与M炚w对，则它?yu)是q条增广路径的终点；反之Q如果点B已与点C配对Q那么这条增q\径就是从A到BQ再从B到CQ再加上“从点C出发的增q\?#8221;。ƈ且，q条从C出发的增q\径中不能与前半部分的增广路径有重复的炏V?br>
比如?中，我们要寻找一条从3出发的增q\径，要做以下3步：(x)
(1)首先?出发Q它能连到的点只?Q?在图1中已l与2配对Q所以目前的增广路径是3->6->2再加上从2出发的增q\径?br>(2)?出发Q它能连到的不与前半部分路径重复的点只有5Q而且5实在原匚w中没有与2配对。所以从2q到5。但5在图1中已l与1配对Q所以目前的增广路径?->6->2->5->1再加上从1出发的增q\径?br>(3)?出发Q能q到的不与自已配对ƈ且不与前半部分\径重复的点只?。因?在图1中没有与M炚w对，所以它?yu)是l点。所以最l的增广路径?->6->2->5->1->4?br>
但是严格地说Q以上过E中?出发的增q\径（2->5->1->4Q和?出发的增q\径（1->4Qƈ不是真正的增q\径。因为它们不W合前面讲过的增q\径的W?条性质Q它们的L(fng)都是已经配过对的炏V我们在q里U它们ؓ(f)“增广路径”只是Z方便说明整个搜寻的过E。而这两条路径本n只能是两个不ؓ(f)外界所知的子过E的q回l果?br>昄Q从上面的例子可以看出，搜寻增广路径的方法就是DFSQ可以写成一个递归函数。当Ӟ用BFS也完全可以实现?br>
xQ理论基部䆾讲完了。但是要完成匈牙利算法，q需要一个重要的定理Q?br>
如果从一个点A出发Q没有找到增q\径，那么无论再从别的点出发找到多增q\径来改变现在的匹配，从A出发都永q找不到增广路径?br>
初始时最大匹配ؓ(f)I?br>for 二分囑ַ半边的每个点i
do 从点i出发L增广路径。如果找刎ͼ则把它取反（卛_加了M匚w敎ͼ?wbr>
如果二分囄左半边一共有n个点Q那么最多找n条增q\径。如果图中共有m条边Q那么每找一条增q\径（DFS或BFSQ时最多把所有边遍历一遍，所花时间也是m。所以ȝ旉大概是OQn * mQ?br>
]]>
//一个数l没有初始化Qwrong了N?wbr>
//很多人都是用匈牙利算法做的，偶也准备学学传说中的匈牙利算?wbr>
#include<iostream>
using namespace std;
int h,w,flag,res,node;
int arr[500][500],map[50][20];
int q[10000],pre[10000],used[500];
int dx[]={-1,1,0,0};
int dy[]={0,0,-1,1};
int path(int s) //L增广路径
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head<tail)
{ temp=tail;
for(i=head;i<temp;i++)
{ u=q[i];
if(u==1)
return 1;
for(j=0;j<node;j++)
if(used[j]==0 && arr[u][j]>0)
{pre[j]=u;
used[j]=1;
q[tail++]=j;
}
}
head=temp;
}
return 0;
}
void ford_fulkerson() //修改增光路径上边的残留容量，记录匚w的结?br>{ int i,j,u,v,min,x,y;
min=INT_MAX;
u=pre[1];
v=1;
while(u>=0)
{if(arr[u][v]<min)
min=arr[u][v];
v=u;
u=pre[u];
}
u=pre[1];
v=1;
while(u>=0)
{ arr[u][v]=arr[u][v]-min;
arr[v][u]=arr[v][u]+min;
v=u;
u=pre[u];
}
res=res+min;
}
int main()
{int i,j,k,Case,x,y;
char c;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&Case);
while(Case--)
{ flag=0;
res=0;
node=2;
scanf("%d%d",&h,&w);
memset(map,0,sizeof(map));
memset(used,0,sizeof(used));
memset(arr,0,sizeof(arr));
for(i=0;i<h;i++)
{getchar();
for(j=0;j<w;j++)
{ scanf("%c",&c);
if(c=='*')
map[i][j]=node++;
}
}
for(i=0;i<h;i++) //构图建模Q抽象成二分囑配的问题
for(j=0;j<w;j++)
{ if(map[i][j] && !used[map[i][j]])
{ arr[0][map[i][j]]=1;
used[map[i][j]]=1;
for(k=0;k<4;k++)
{ x=i+dx[k];
y=j+dy[k];
if(x>=0 && x<h && y>=0 && y<w && map[x][y])
{arr[map[i][j]][map[x][y]]=1;
arr[map[x][y]][1]=1;
used[map[x][y]]=1;
}
}
}
}
while(!flag)
{ memset(used,0,sizeof(used));
memset(pre,-1,sizeof(pre));
if(path(0))
ford_fulkerson();
else
flag=1;
}
printf("%d\n",node-2-res);
}
return 0;
}
]]>
//很多人把它做成二分图匚w
//但貌似用最大流也能求出?br>#include<iostream>
#include<string>
#include<map>
using namespace std;
int nr,np,na,flag,res,node;
int arr[402][402];
int q[1000],pre[1000],used[402];
map <string,int> PR;
int path(int s)
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head<tail)
{ temp=tail;
for(i=head;i<temp;i++)
{ u=q[i];
if(u==1)
return 1;
for(j=0;j<node;j++)
if(used[j]==0 && arr[u][j]>0)
{pre[j]=u;
used[j]=1;
q[tail++]=j;
}
}
head=temp;
}
return 0;
}
void ford_fulkerson()
{ int i,j,u,v,min,x,y;
min=INT_MAX;
u=pre[1];
v=1;
while(u>=0)
{if(arr[u][v]<min)
min=arr[u][v];
v=u;
u=pre[u];
}
u=pre[1];
v=1;
while(u>=0)
{ arr[u][v]=arr[u][v]-min;
arr[v][u]=arr[v][u]+min;
v=u;
u=pre[u];
}
res=res+min;
}
int main()
{int u,v,w,i,j;
char str1[25],str2[25];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&nr);
flag=0;
res=0;
node=2;
for(i=0;i<nr;i++)
{ scanf("%s",str1);
if(!PR[str1])
PR[str1]=node++;
arr[0][PR[str1]]++;
}
scanf("%d",&np);
for(i=0;i<np;i++)
{ scanf("%s%s",str1,str2);
if(!PR[str2])
PR[str2]=node++;
arr[PR[str2]][1]++;
}
scanf("%d",&na);
for(i=0;i<na;i++)
{ scanf("%s%s",str1,str2);
if(!PR[str1])
PR[str1]=node++;
if(!PR[str2])
PR[str2]=node++;
arr[PR[str2]][PR[str1]]=INT_MAX;
}
while(!flag)
{ memset(used,0,sizeof(used));
memset(pre,-1,sizeof(pre));
if(path(0))
ford_fulkerson();
else
flag=1;
}
printf("%d\n",np-res);
return 0;
}
]]>
基本思\Q把各条弧上单位量的费用看成某U长?用求解最短\问题的方法确定一条自V1至Vn的最短\;在将q条最短\作ؓ(f)可扩充\,用求解最大流问题的方法将其上的流量增x大可能?而这条最短\上的量增加?其上各条弧的单位量的费用要重新定,如此多次q代,最l得到最费用最大流.
q加法Q?br>
1) l定目标量F?#8734;,l定最费用的初始可行?0
2) 若V(f)=F,停止,f为最费用流;否则?3).
3) 构?相应的新的费用有向图W(wng)(fij),在W(fij)LVs到Vt的最费用有向\P(最短\),沿P增加f的流量直到F,?2);若不存在从Vs到Vt的最费用的有向路P,停止.f是最费用最大流.
具体解题步骤Q?br>
讑֛中双U所C\径ؓ(f)最短\径，费用有向图ؓ(f)WQfijQ．
在图(a)中给出零?f,在图(b)中找到最费用有向\,修改?a)中的可行?δ=min{4,3,5}=3,得图(c),再做?c)的调整容量图,再构造相应的新的最费用有向\得图(d), 修改?c)中的可行? δ=min{1,1,2,2}=1,得图(e),以此cL,一直得到图(h),在图(h)中以无最费用有向\,停止,l计?
?h)?最费?1*4+3*3+2*4+4*1+1*1+4*2+1*1+3*1=38
?g)?最大流=5
最大流问题仅注意网l流的流通能力，没有考虑通的费用。实际上费用因素是很重要的。例如在交通运输问题中Q往往要求在完成运输Q务的前提下，L一个总运输费用最省的q输Ҏ(gu)Q这是最费用流问题。如果只考虑单位货物的运输费用，那么q个问题变成最短\问题。由此可见，最短\问题是最费用流问题的基。现已有一pd求最短\的成功方法。最费用流(或最费用最大流)问题 Q可以交替用求解最大流和最短\两种Ҏ(gu)Q通过q代得到解决?br>
//老老实实看了一天的书，l于敲出了第一个关于网l流的程?wbr style="LINE-HEIGHT: 1.3em">
//庆祝的零的H破
#include<iostream>
using namespace std;
int n,np,nc,m,flag,res;
int arr[110][110];
int q[10000],pre[10000],used[110];
int path(int s)
{ int u,head,tail,temp,i,j;
head=tail=0;
q[tail++]=s;
used[s]=1;
while(head<tail)
{ temp=tail;
for(i=head;i<temp;i++)
{ u=q[i];
if(u==n+1)
return 1;
for(j=0;j<=n+1;j++)
if(!used[j] && arr[u][j]>0)
{pre[j]=u;
used[j]=1;
q[tail++]=j;
}
}
head=temp;
}
return 0;
}
void ford_fulkerson()
{ int i,j,u,v,min;
min=INT_MAX;
u=pre[n+1];
v=n+1;
while(u>=0)
{if(arr[u][v]<min)
min=arr[u][v];
v=u;
u=pre[u];
}
u=pre[n+1];
v=n+1;
while(u>=0)
{ arr[u][v]=arr[u][v]-min;
arr[v][u]=arr[v][u]+min;
v=u;
u=pre[u];
}
res=res+min;
}
int main()
{int u,v,w,i,j;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d%d%d%d",&n,&np,&nc,&m))!=EOF)
{ flag=0;
res=0;
memset(arr,0,sizeof(arr));
for(i=0;i<m;i++)
{ while(getchar()!='(');
scanf("%d,%d)%d",&u,&v,&w);
arr[u][v]=w;
}
for(i=0;i<np;i++)
{ while(getchar()!='(');
scanf("%d)%d",&v,&w);
arr[n][v]=w;
}
for(i=0;i<nc;i++)
{ while(getchar()!='(');
scanf("%d)%d",&u,&w);
arr[u][n+1]=w;
}
while(!flag)
{ memset(used,0,sizeof(used));
memset(pre,-1,sizeof(pre));
if(path(n))
ford_fulkerson();
else
flag=1;
}
printf("%d\n",res);
}
return 0;
}
]]>
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
int map[26][26],v[26],used[26],flag,n,total;
char str[27];
void sort(int i,int m)
{ int k;
if(total==n)
{ flag=2;
return ;
}
for(k=0;k<n && !flag;k++)
{ if(map[i][k]==0)
continue;
if(v[k])
{ flag=1;
return ;
}
str[m]=k+65;
total++;
v[k]=1;
sort(k,m+1);
if(flag)
return ;
v[k]=0;
total--;
}
}
int main()
{int row,i,j,a,b,k,l;
char s[4];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(1)
{ scanf("%d%d",&n,&row);
if(n==0 && row==0)
break;
flag=0;
memset(map,0,sizeof(map));
memset(used,0,sizeof(used));
for(k=1;k<=row;k++)
{ scanf("%s",s);
if(!flag)
{memset(v,0,sizeof(v));
a=s[0]-65;
b=s[2]-65;
used[a]=1;
used[b]=1;
map[a][b]=1;
for(i=0;i<n && !flag;i++)
{ if(used[i]==0)
break;
total=1;
v[i]=1;
str[0]=i+65;
sort(i,1);
v[i]=0;
}
if(flag==1)
printf("Inconsistency found after %d relations.\n",k);
else if(flag==2)
{printf("Sorted sequence determined after %d relations: ",k);
for(i=0;i<n;i++)
printf("%c",str[i]);
printf(".\n");
flag=1;
}
}
}
if(!flag)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
// 改用floyd_warshall法才过
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
typedef struct Node{
int d;
char c;
}Node;
int map[26][26],used[26],flag,n;
Node node[26];
int cmp(const void *a, const void *b)
{ return (*(Node *)a).d-(*(Node *)b).d;
}
void check()
{int i,j;
for(i=0;i<n;i++)
{ if(used[i]==0)
return ;
for(j=0;j<n;j++)
if(map[i][j])
node[j].d++;
}
qsort(node,n,sizeof(Node),cmp);
for(i=0;i<n;i++)
if(node[i].d!=i)
return ;
flag=2;
}
int main()
{int row,i,j,a,b,k,h;
char s[4];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(1)
{ scanf("%d%d",&n,&row);
if(n==0 && row==0)
break;
flag=0;
memset(map,0,sizeof(map));
for(h=1;h<=row;h++)
{ scanf("%s",s);
if(!flag)
{a=s[0]-65;
b=s[2]-65;
used[a]=1;
used[b]=1;
for(i=0;i<n;++i)
{node[i].d=0;
node[i].c=i+65;
}
if(map[b][a]==1 || a==b)
{ printf("Inconsistency found after %d relations.\n",h);
flag=1;
}
else
map[a][b]=1;
for(k=0;k<26;++k)
for(i=0;i<26;++i)
for(j=0;j<26;++j)
map[i][j]=(map[i][j]||(map[i][k]&&map[k][j]));
if(!flag)
check();
if(flag==2)
{printf("Sorted sequence determined after %d relations: ",h);
for(i=0;i<n;i++)
printf("%c",node[i].c);
printf(".\n");
}
}
}
if(!flag)
printf("Sorted sequence cannot be determined.\n");
}
return 0;
}
]]>
//1,当前未U_最短\的符合要求的距离最短结点纳入最短\;
//2,所有与当前U_的结Ҏ(gu)兌q且未被U_最短\的结Ҏ(gu)短距进行更新?
//图论中另一个求最生成树(wi)的的l典法Prim法与Dijq程极其cMQ都是贪心思想?
//只是一个是寚w点的选择Q另外一个是对边的选择?
import java.util.*;
public class Main
{ public static int[][] e;
public static int[] dis;
public static int[] used;
public static int[] level;
public static int n,m;
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
int x,t;
e = new int[101][101];
dis = new int[101];
used = new int[101];
level = new int[101];
m=cin.nextInt();
n=cin.nextInt();
for(int i=1;i<=n;i++)
{ e[0][i]=cin.nextInt();
level[i]=cin.nextInt();
x=cin.nextInt();
for(int j=0;j<x;j++)
{ t=cin.nextInt();
e[t][i]=cin.nextInt();
}
}
solve();
}
public static void solve()
{ int max,result;
result=e[0][1];
for(int i=1;i<=n;i++)
{ max=level[i];
for(int j=1;j<=n;j++)
if(level[j]>max || level[j]<max-m)//判断所交易的h的等U是否符合题目所q的条g
used[j]=1;//不符?
else
used[j]=0; //W合
dijkstra();
if(result>dis[1]) //比较每次所求的费用
result=dis[1];
}
System.out.println(result);
}
public static void dijkstra()
{ int min,temp,k;
for(int i=1;i<=n;i++)
dis[i]=e[0][i];
for(int i=1;i<=n;i++)
{ min=0x7FFFFFFF;
k=0;
for(int j=1;j<=n;j++)//扑և代h(hun)最的?
if(used[j]==0 && dis[j]<min)
{min=dis[j];
k=j;
}
if(k==0)
break;
used[k]=1;
for(int j=1;j<=n;j++)//更新其节点的?
if(used[j]==0 && e[k][j]>0 && min+e[k][j]<dis[j])
dis[j]=min+e[k][j];
}
}
}
]]>
//一眼就可以看出来用folyd_warshell,我却用dijkstraQ调试了N?wbr>
//首先引进一个辅助向量d[i]表示当前所扑ֈ的从L(fng) v到每个终点的最短\径的长度.
它的初态ؓ(f):若从v到vi有狐,则d[i]为弧上的?否则d[i]为inifity.昄?nbsp;
//一条最短\径或者是?s,x),或者是中间只经qs的顶点而最后到N点x的\?所?wbr>
//d[x]=min{d[x],d[s]+arcs[s][x]}
#include<iostream>
using namespace std;
int used[101],map[101][101],d[101],n,flag,max1,max2,v;
void solve(int i)
{ int j,k,min,v0,v1;
for(j=1;j<=n;j++)
{ used[j]=0;
if(map[i][j]==0)
d[j]=1000000000;
else
d[j]=map[i][j];
}
used[i]=1;
while(1)
{ min=1000000000;
v0=0;
for(j=1;j<=n;j++)
{ if(used[j]==0 && d[j]<min)
{min=d[j];
v0=j;
}
}
if(v0==0)
break;
used[v0]=1;
for(j=1;j<=n;j++)
{if(used[j]==0 && map[v0][j] && min+map[v0][j]<d[j])
d[j]=min+map[v0][j];
}
}
max1=0;
for(k=1;k<=n;k++)
{ if(k==i)
continue;
if(d[k]>max1)
{max1=d[k];
v1=i;
}
}
if(max1<max2)
{ flag=1;
v=v1;
max2=max1;
}
}
int main()
{ int m,i,j,a,b;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(cin>>n,n!=0)
{ memset(map,0,sizeof(map));
flag=0;
for(i=1;i<=n;i++)
{ cin>>m;
for(j=1;j<=m;j++)
{ cin>>a>>b;
map[i][a]=b;
}
}
max2=1000000000;
v=0;
for(i=1;i<=n;i++)
solve(i);
if(n==1)
{ flag=1;
v=1;
max2=0;
}
if(flag)
cout<<v<<" "<<max2<<endl;
else
cout<<"disjoint"<<endl;
}
return 0;
}
]]>
//而这个题很多人都用dijkstra,我就用floyd_warshall;
//两个字，flody的代码敲h是单，但效率比较的低，复杂度是(n^3)
#include<iostream>
#include<cmath>
#include <algorithm>
using namespace std;
int main()
{ int n,Case,i,j,k;
int x[201],y[201];
int map[201][201];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
Case=1;
while(scanf("%d",&n),n!=0)
{ memset(map,0,sizeof(map));
for(i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for( i=1;i<=n;i++)
for( j=i+1;j<=n;j++)
{ map[i][j]=abs((x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]));
map[j][i]=map[i][j];
}
for( k=1;k<=n;k++)
for( i=1;i<=n;i++)
for( j=i+1;j<=n;j++)
{ if(map[i][k] && map[k][j] && map[i][k]<map[i][j] && map[k][j]<map[i][j])
{ if(map[i][k]>map[k][j])
map[i][j]=map[i][k];
else
map[i][j]=map[k][j];
}
map[j][i]=map[i][j];
}
printf("Scenario #%d\n",Case++);
printf("Frog Distance = %.3lf\n\n",sqrt(map[1][2]*1.0));
}
return 0;
}
]]>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{ int n,m,flag,Case;
double temp,array[31][31];
char s1[100],s2[100],str[31][100];
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
Case=1;
while(scanf("%d",&n),n!=0)
{ flag=0;
memset(array,0,sizeof(array));
for(int i=1;i<=n;i++)
scanf("%s",str[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{int k,j;
scanf("%s%lf%s",s1,&temp,s2);
for(int h=1;h<=n;h++)
{ if(!strcmp(str[h],s1))
k=h;
if(!strcmp(str[h],s2))
j=h;
}
array[k][j]=temp;
}
for( int k=1;k<=n;k++)
for( int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(array[i][j]<array[i][k]*array[k][j])
array[i][j]= array[i][k]*array[k][j];
for( int i=1;i<=n;i++)
if(array[i][i]>1)
{ flag=1;
break;
}
if(flag)
printf("Case %d: Yes\n",Case++);
else
printf("Case %d: No\n",Case++);
}
return 0;
}
]]>
//一定要坚持下去
#include<iostream>
#define eps 1e-8
using namespace std;
typedef struct E{
int v,u;
double r,c;
};
int n,m,s,num;
double money,d[101];
E e[201];
bool bellman()
{ int flag;
memset(d,0,sizeof(d));
d[s]=money;
while(d[s]<=money+eps)
{ flag=0;
for(int i=0;i<num;i++)
if(d[e[i].v]+eps<(d[e[i].u]-e[i].c) * e[i].r)
{ d[e[i].v]=(d[e[i].u]-e[i].c)*e[i].r;
flag=1;
}
if(!flag)
return d[s]>money+eps;
}
return true;
}
int main()
{int V,U;
double cv,rv,cu,ru;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d%d%d%lf",&n,&m,&s,&money))!=EOF)
{num=0;
for(int i=1;i<=m;i++)
{scanf("%d%d%lf%lf%lf%lf",&U,&V,&rv,&cv,&ru,&cu);
e[num].v=V;
e[num].u=U;
e[num].r=rv;
e[num++].c=cv;
e[num].v=U;
e[num].u=V;
e[num].r=ru;
e[num++].c=cu;
}
if(bellman())
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
]]>
//其实是求最生成树(wi)Q用l典的prim法
#include<iostream>
using namespace std;
int array[2001][2001],total;
int used[2001],dis[2001];
char truck[2001][8];
void prim(int n)
{ int v,min;
for(int i=1;i<=n;i++)
{used[i]=0;
dis[i]=array[1][i];
}
used[1]=1;
while(true)
{ min=INT_MAX;
v=0;
for(int i=1;i<=n;i++)
if(!used[i] && dis[i]<min) //在S的补集选出权最的?wbr>
{ min=dis[i];
v=i;
}
if(v==0)
break;
total=total+min;
used[v]=1; //加入S集合
for(int j =1;j<=n;j++)
if(!used[j] && dis[j]>array[v][j]) //更新最权边的?wbr>
dis[j]=array[v][j];
}
}
int main()
{int n,sum;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while(scanf("%d",&n),n!=0)
{for(int i=1;i<=n;i++)
scanf("%s",truck[i]);
memset(array,0,sizeof(array));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{ if(i==j || array[i][j])
continue;
sum=0;
for(int k=0;k<7;k++)
if(truck[i][k]!=truck[j][k])
sum++;
array[i][j]=sum;
array[j][i]=sum;
}
total=0;
prim(n);
printf("The highest possible quality is 1/%d.\n",total);
}
return 0;
}
]]>
//只是E稍改了一下前一题的代码Q最生成树(wi)问题
#include<iostream>
using namespace std;
int array[101][101],total;
int used[101],dis[101];
void prim(int n)
{ int v,min;
for(int i=1;i<=n;i++)
{used[i]=0;
dis[i]=array[1][i];
}
used[1]=1;
while(true)
{ min=INT_MAX;
v=0;
for(int i=1;i<=n;i++)
if(!used[i] && dis[i]<min)
{ min=dis[i];
v=i;
}
if(v==0)
break;
total=total+min;
used[v]=1;
for(int j =1;j<=n;j++)
if(!used[j] && dis[j]>array[v][j])
dis[j]=array[v][j];
}
}
int main()
{int n,sum;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
while((scanf("%d",&n))!=EOF)
{for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&array[i][j]);
total=0;
prim(n);
printf("%d\n",total);
}
return 0;
}
]]>
#include<iostream>
using namespace std;
int array[501][501],total;
int used[501],dis[501];
void prim(int n)
{ int v,min;
for(int i=1;i<=n;i++)
{used[i]=0;
dis[i]=array[1][i];
}
used[1]=1;
while(true)
{ min=INT_MAX;
v=0;
for(int i=1;i<=n;i++)
if(!used[i] && dis[i]<min)
{ min=dis[i];
v=i;
}
if(v==0)
break;
if(min>total)
total=min;
used[v]=1;
for(int j =1;j<=n;j++)
if(!used[j] && dis[j]>array[v][j])
dis[j]=array[v][j];
}
}
int main()
{int m,n,sum;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&m);
while(m--)
{ scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&array[i][j]);
total=0;
prim(n);
printf("%d\n",total);
}
return 0;
}
]]>
using namespace std;
typedef struct Node
{ int u,v,t;
}Node;
Node e[25000];
int n,m,w,en;
bool bellmanford()
{ bool flag;
int dis[1001];
for(int i=0;i<n-1;i++)
{ flag=false;
for(int j=0;j<en;j++)
if(dis[e[j].v]>dis[e[j].u]+e[j].t)
{dis[e[j].v]=dis[e[j].u]+e[j].t;
flag=true;
}
if(!flag)
break;
}
for(int i=0;i<en;i++)
if( dis[e[i].v]>dis[e[i].u]+e[i].t)
return true;
return false;
}
int main()
{int Case ,u,v,t;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&Case);
while(Case--)
{ scanf("%d%d%d",&n,&m,&w);
en=0;
for(int i=1;i<=m;i++)
{ scanf("%d%d%d",&u,&v,&t);
e[en].u=u;
e[en].v=v;
e[en++].t=t;
e[en].u=v;
e[en].v=u;
e[en++].t=t;
}
for(int i=1;i<=w;i++)
{ scanf("%d%d%d",&u,&v,&t);
e[en].u=u;
e[en].v=v;
e[en++].t=-t;
}
if(bellmanford())
puts("YES");
else
puts("NO");
}
return 0;
}
|
Bellman-Ford 法及其优化
Bellman-Ford法与另一个非常著名的Dijkstra法一P用于求解单源Ҏ(gu)短\径问题?/span>Bellman-ford法除了可求解边权均非负的问题外Q还可以解决存在负权边的问题Q意义是什么，好好思考）Q?/span>Dijkstra法只能处理Ҏ(gu)非负的问题，因此 Bellman-Ford法的适用面要q泛一些。但是，原始?/span>Bellman-Ford法旉复杂度ؓ(f) OQ?/span>VEQ?/span>,?/span>Dijkstra法的时间复杂度高，所以常常被众多的大学算法教U书所忽略Q就q经典的《算法导论》也只介l了基本?/span>Bellman-Ford法Q在国内常见的基本信息学奥赛教材中也均未提及Q因此该法的知名度与被掌握度都不如Dijkstra法。事实上Q有多种形式?/span>Bellman-Ford法的优化实现。这些优化实现在旉效率上得到相当提升，例如q一两年被热捧的SPFAQ?/span>Shortest-Path Faster Algoithm 更快的最短\径算法）法的时间效率甚至由?/span>Dijkstra法Q因此成Z息学奥赛选手l常讨论的话题。然而，限于资料匮乏Q有?/span>Bellman-Ford法的诸多问题常常困扰奥赛选手。如Q该法值得掌握么？怎样用编E语a具体实现Q有哪些优化Q与SPFA法有关pMQ本文试囑֯Bellman-Ford法做一个比较全面的介绍。给出几U实现程序，从理论和实测两方面分析他们的旉复杂度，供大家在备战省选和后箋?/span>noi时参考?/span>
Bellman-Ford法思想Bellman-Ford法能在更普遍的情况下（存在负权边）解决单源Ҏ(gu)短\径问题。对于给定的带权Q有向或无向Q图 G=Q?/span>V,EQ，其源点ؓ(f)sQ加权函?/span> w?/span> 辚w E 的映。对?/span>Gq行Bellman-Ford法的结果是一个布?yu)(dng)|表明图中是否存在着一个从源点s可达的负权回路?/span>若不存在q样的回路，法给Z源点s?/span> ?/span>G的Q意顶?/span>v的最短\?/span>d[v]?/span> Bellman-Ford法程分ؓ(f)三个阶段Q?/span>Q?Q?span style="FONT: 7pt Times New Roman"> 初始化：(x)除源点外的所有顶点的最短距M计?/span> d[v] ←+∞, d[s] ←0; Q?Q?span style="FONT: 7pt Times New Roman"> q代求解Q反复对辚wE中的每条边进行松弛操作，使得点集V中的每个点v的最短距M计值逐步D其最短距；Q运行|v|-1ơ） Q?Q?span style="FONT: 7pt Times New Roman"> 验负权回路：(x)判断辚wE中的每一条边的两个端Ҏ(gu)否收敛。如果存在未收敛的顶点，则算法返?/span>falseQ表明问题无解；否则法q回trueQƈ且从源点可达的顶?/span>v的最短距M存在 d[v]中?/span>
法描述如下Q?/span> Bellman-Ford(G,w,s) Q?/span>boolean //?/span>G Q边?/span> 函数 w Q?/span>s为源?/span> 1 for each vertex v ∈ VQGQ?do //初始?span style="mso-spacerun: yes"> 1阶段 2 d[v] ←+∞ 3 d[s] ←0; //1阶段l束 4 for i=1 to |v|-1 do //2阶段开始，双重循环?/span> 5 for each edgeQu,vQ?∈E(G) do //辚w数组要用刎ͼID每条辏V?/span> 6 If d[v]> d[u]+ w(u,v) then //村ּ判断 7 d[v]=d[u]+w(u,v) //村ּ操作 2阶段l束 8 for each edgeQu,vQ?∈E(G) do 9 If d[v]> d[u]+ w(u,v) then 10 Exit false 11 Exit true
下面l出描述性证明：(x) 首先指出Q图的Q意一条最短\径既不能包含负权回\Q也不会(x)包含正权回\Q因此它最多包?/span>|v|-1条边?/span> 其次Q从源点s可达的所有顶点如?/span> 存在最短\径，则这些最短\径构成一个以s为根的最短\径树(wi)?/span>Bellman-Ford法的P代松弛操作，实际上就是按点距离s的层ơ，逐层生成q棵最短\径树(wi)的过E?/span> 在对每条边进?span>1遍松弛的时候，生成了从s出发Q层ơ至多ؓ(f)1的那些树(wi)枝。也是_(d)扑ֈ了与s臛_?条边相联的那些顶点的最短\径；Ҏ(gu)条边q行W?遍松弛的时候，生成了第2层次的树(wi)枝，是说找Cl过2条边相连的那些顶点的最短\?#8230;…。因为最短\径最多只包含|v|-1 条边Q所以，只需要@环|v|-1 ơ?/span> 每实施一ơ松弛操作，最短\径树(wi)上就?x)有一层顶点达到其最短距，此后q层点的最短距d就?x)一直保持不变，不再受后l松弛操作的影响。（但是Q每ơ还要判断松弛，q里费了大量的旉Q怎么优化Q单U的优化是否可行Q） 如果没有负权回\Q由于最短\径树(wi)的高度最多只能是|v|-1Q所以最多经q|v|-1遍松弛操作后Q所有从s可达的顶点必求出最短距R如?d[v]仍保?+∞Q则表明从s到v不可达?/span> 如果有负权回路，那么W?span> |v|-1 遍松弛操作仍然会(x)成功Q这Ӟ负权回\上的点不会(x)收敛?/span>
例如对于上图Q边上方框中的数字代表权|点A,B,C之间存在负权回\。S是源点，点中数字表C行Bellman-Ford法后各点的最短距M计倹{?/span> 此时d[a]的gؓ(f)1Q大于d[c]+w(c,a)的?2Q由此d[a]可以村ּ?2Q然后d[b]又可以松弛ؓ(f)-5,d[c]又可以松弛ؓ(f)-7.下一个周期，d[a]又可以更Cؓ(f)更小的|q个q程永远不会(x)l止。因此，在P代求解最短\径阶D늻束后Q可以通过验边集E的每条边(u,v)是否满关系?span style="mso-spacerun: yes"> d[v]> d[u]+ w(u,v) 来判断是否存在负权回路?br> 二、基?/span> Bellman-Ford 法?/span> pascal实现?/span>?/span> bellmanford.pas 文g?/span> 三、基本算法之上的优化?/span>分析 Bellman-Ford法Q不隄出，外层循环QP代次敎ͼ|v|-1实际上取得是上限。由上面对算法正性的证明可知Q需要的q代遍数{于最短\径树(wi)的高度。如果不存在负权回\Q^均情况下的最短\径树(wi)的高度应该远q小?/span> |v|-1Q在此情况下Q多余最短\径树(wi)高的q代遍数是旉上的费Q由此，可以依次来实施优化?/span> 从细节上分析Q如果在某一遍P代中Q算法描qCW?/span>7行的村ּ操作未执行，说明该遍q代所有的辚w没有被松弛。可以证明（怎么证明Q）Q至此后Q边集中所有的辚w不需要再被松弛，从而可以提前结束P代过E。这P优化的措施就非常单了?/span> 讑֮一个布?yu)(dng)型标志变?/span> relaxedQ初gؓ(f)false。在内层循环中，仅当有边被成功松弛时Q将 relaxed 讄?/span>true。如果没有边被松弛，则提前结束外层@环。这一改进可以极大的减外层@环的q代ơ数。优化后?/span> bellman-ford函数如下?/span> function bellmanford(s:longint):boolean; begin for i:=1 to nv do d[i]:=max; d[s]:=0; for i:=1 to nv-1 do begin relaxed:=false; for j:=1 TO ne do if(d[edges[j].s]<>max) and (d[edges[j].e]>d[edges[j].s]+edges[j].w) then begin d[edges[j].e]:=d[edges[j].s]+edges[j].w ; relaxed:=true; end; if not relaxed then break; end; for i:=1 to ne do if d[edges[j].e]>d[edges[j].s]+edges[j].w then exit(false); exit(true); end; q样看似q_的优化，?x)有怎样的效果呢Q有研究表明Q对于随机生成数据的q_情况Q时间复杂度的估公式ؓ(f) 1.13|E| if |E|<|V| 0.95*|E|*lg|V| if |E|>|V| 优化后的法在处理有负权回\的测试数据时Q由于每ơ都?x)有边被村ּQ所?/span>relaxed每次都会(x)被置?/span>trueQ因而不可能提前l止外层循环。这对应了最坏情况，其时间复杂度仍旧?/span>O(VE)?/span> 优化后的法的时间复杂度已经和用二叉堆优化的Dijkstra法相近了，而编码的复杂E度q比后者低。加?/span>Bellman-Ford法能处理各U边值权情况下的最短\径问题，因而还是非怼U的?/span>Usaco3.2.6 的程序见bellmanford_1.pas 四?/span>SPFA 法 SPFA是目前相当优U的求最短\径的法Q值得我们掌握?/span> SPFA?/span>Bellman-Ford法优化的关键之处在于意识到Q?span style="COLOR: #ff6600">只有那些在前一遍松弛中改变了距M计值的点，才可能引起他们的L点的距离估计值的改变?/span>因此Q用一个先q先出的队列来存放被成功村ּ的顶炏V初始时Q源?/span>s入队。当队列不ؓ(f)I时Q取出对首顶点，对它的邻接点q行村ּ。如果某个邻接点村ּ成功Q且该邻接点不在队列中，则将其入队。经q有限次的松弛操作后Q队列将为空Q算法结束?/span>SPFA法的实玎ͼ需要用C个先q先出的队列 queue 和一个指C顶Ҏ(gu)否在队列中的 标记数组 mark。ؓ(f)了方便查找某个顶点的L点，N用(f)界表存储?/span> E序存储?/span> spfa.pas中。以usaco 3.2.6 试题2Z。用L表写的程序?/span> 需要注意的是：(x)仅当图不存在负权回\ӞSPFA能正常工作。如果图存在负权回\Q由于负权回路上的顶Ҏ(gu)法收敛，L点在入队和出队往q，队列无法为空Q这U情况下SPFA无法正常l束?/span> 判断负权回\?/span>Ҏ(gu)很多Q世间流传最q的是记录每个结点进队次敎ͼ过|V|ơ表C有负权 关于SPFA的时间复杂度Q不好准估计，一般认为是 OQ?/span>kEQ，k是常?/span> 五、时间效率实?/span>上述介绍?/span>Bellman-Ford法及两U的优化Q只是在理论上分析了旉复杂度，用实际的数据试Q会(x)有什么结果呢Qؓ(f)此，我们选择 usaco 3.2.6?/span> Spfa的时间效率还是很高的。ƈ?/span>spfa的编E复杂度要比Dijksta+heap优化要好的多?/span> 六、结?/span>l过优化Bellman-Ford法是非怼化的求单源最短\径的法Q?/span>SPFA旉效率要优于第一U优化Ş式，但第一U优化Ş式的~码复杂度低?/span>SPFA。两U优化Ş式的~程复杂度都低于Dijkstra法。如果在判断是否存在负权回\Q推荐用第一U优化Ş式，否则推荐使用SPFA?/span> |
]]>
#include<iostream>
#include<algorithm>
using namespace std;
typedef struct Node
{ int label;
int cnt;
int leaf[200];
};
Node tree[200];
int solve(int i)
{ int stone[200],result,temp;
if(tree[i].cnt==0)
return 1;
for(int j=0;j<tree[i].cnt;j++)
stone[j]=solve(tree[i].leaf[j]);
sort(stone,stone+tree[i].cnt);
result=stone[tree[i].cnt-1];
temp=result-1;
for(int k=tree[i].cnt-2;k>=0;k--)
{ if(temp-stone[k]>=0)
temp--;
else
{result=result+stone[k]-temp;
temp=stone[k]-1;
}
}
return result;
}
int main()
{ int n,m;
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&n);
while(n--)
{ scanf("%d",&m);
for(int i=1;i<=m;i++)
{ scanf("%d%d",&tree[i].label,&tree[i].cnt);
for(int j=0;j<tree[i].cnt;j++)
scanf("%d",&tree[i].leaf[j]);
}
printf("%d\n",solve(1));
}
return 0;
}
]]>