USACO/concom

来自NOCOW

[编辑] 分析

以下，由basky给出： DFS0.03秒就可以了。就这题的数据规模来说，DFS应该挺好的.
USER: é›„ åº” [bianzhi1] TASK: concom LANG: PASCAL

Compiling... Compile: OK

Executing...

  Test 1: TEST OK [0.000 secs, 696 KB]
  Test 2: TEST OK [0.000 secs, 696 KB]
  Test 3: TEST OK [0.000 secs, 696 KB]
  Test 4: TEST OK [0.000 secs, 696 KB]
  Test 5: TEST OK [0.000 secs, 696 KB]
  Test 6: TEST OK [0.000 secs, 696 KB]
  Test 7: TEST OK [0.000 secs, 696 KB]
  Test 8: TEST OK [0.000 secs, 696 KB]
  Test 9: TEST OK [0.032 secs, 696 KB]

All tests OK. Your program ('concom') produced all correct answers! This is your submission #6 for this problem. Congratulations!

DFS还是很简单的：只要存入一个邻接矩阵，然后

 for i:=1 to n do
 begin
   fillchar(c,sizeof(c),0);
   fillchar(u,sizeof(u),false);
   dfs(i);
   for j:=1 to n do
     if (i<>j)and(c[j]>50) then writeln(i,' ',j);
 end;

DFS的过程如下：

 procedure dfs(x:integer);
 var  i:integer;
 begin
   u[x]:=true;
   for i:=1 to n do
     inc(c[i],r[x,i]);
   for i:=1 to n do
     if (c[i]>50)and not u[i] then dfs(i);
 end;

//wrriten by basky
全代码：见页尾Pascal代码的链接

---

算法类似Floyd,三重循环然后判断

 for k:=1 to 100 do
   for i:=1 to 100 do
     for j:=1 to 100 do
        if (f[i,k]>=50) and (not vis[i,k,j]) then
         begin
           f[i,j]:=f[i,j]+f[k,j];
           vis[i,k,j]:=true;
         end;

要注意不要重复计数，所以用一个三维数组vis记录i,j,k三数是否已使用

PS:因为有第三种情况所以算法要多次执行，循环十次就可出解

                                                     --By D.puppet

——楼上的算法可能有误……=。=！

floyd的算法我认为是对的，用了动态规划，没想不要乱说行不行！--by dam

这道题用floyd确实有错，参考代码中利用floyd算法的pascal程序能AC，有运气的成分。把第二个pascal程序的floyd函数中下述语句：

   for k:=100 downto 1 do
     for i:=100 downto 1 do
       if i<>k then
         for j:=100 downto 1 do

改为：

   for k:=1 to 100 do
     for i:=1 to 100 do
       if i<>k then
         for j:=1 to 100 do

程序就会在第6个点WA掉～～原作者能过这道题，运气真的非常好～～ floyd算法在这道题目中回溯不完整，参考代码通过多次调用floyd算法来弥补回溯，但是原理上还是错误的。（参考代码中连续调用了10次floyd，我不知道这个10次原作者是怎么算出来的）

我是如下的floyd： for k:=1 to sums do

for i:=1 to sums do

for j:=1 to sums do

if {(dp[i,j]>50)or}(i=j) then continue

else

if (dp[i,k]>50)and (not vst[i,k,j]){and(yy[k,j]>0)} then

begin

dp[i,j]:=dp[i,j]+yy[k,j];

vst[i,k,j]:=true;

done:=false;

end;

(yy[i,j]表示i到j的直接控制股份) 经测试，似乎1-8都可以8次一下的floyd出解，但第9个点用了50多次floyd……不过可以ac，0.611s。本题确实不可用参考代码中的第二个，虽然ac。如果把to改成downto就wa了。而以上的程序改为downto仍可以0.8s ac。问题似乎在用原floyd时，如果控股在于公司的子公司的子公司，那么这份股票会被加两次。（可以试一下test7，改成downto时会wa），所以每次只能添加公司直接控制的部分。 ——Phoeagon

楼上不要乱讲，有时对于这类直接求时会出现递归的题，常量循环的调整也是不错的选择。——Jollwish

用floyd盲目的增加执行次数并不能保证正确性，只能用BFS或DFS不断迭代求出正解。就好比如果出现了负环，bellman-ford迭代n次无法求出最短路，而SPFA通过不断迭代，能求出“更短”的路。 ——Ambush

直接宽搜. ---zdsoi2

小小总结一句吧，floyd的原理是错的(至于为什么，我想是因为本题不是严谨的传递闭包，所以有各种问题)，新手请直接略过，去看bfs或dfs迭代的算法。当然如同jollwish讲的：这个floyd算法考试时有骗分价值。——CZDleaf

这道题的FLOYD貌似只是近似算法，如果11次以上的传递（只有一条路径），10次循环还是有可能出错的。。。

贪心亦可

       repeat
               flag:=true;
               for i:=1 to n do
                       for j:=1 to n do if i<>j then
                               if(h[i,j]>50)and not k[i,j]then begin
                                       flag:=false;
                                       k[i,j]:=true;
                                       for t:=1 to n do inc(h[i,t],h[j,t]);
                               end;
       until flag;//直接控制
       repeat
               flag:=true;
               for i:=1 to n do
                       for j:=1 to n do
                               if(i<>j)and(k[i,j])then
                               for t:=1 to n do
                                       if(i<>t)and(j<>t)then
                                               if k[j,t]and not k[i,t]then begin
                                                       k[i,t]:=true;
                                                       flag:=false;
                                               end;
       until flag;间接控制

上面的方法貌似不对，代码是不会过的

其实本题暴力穷举也能过,思想简单,但效率不高方法是对于每对i,j,枚举每个公司来更新i是否能控制j 这里还要加几个小的优化,详情可以参照本菜的丑陋代码(ID是noip2012的那个) 我是用PASCAL写的,最后一个点在USACO的评测机上是0.994秒,C/C++应该没问题,PASCAL就很难说了,可能会TLE

看大家的程序，有好多在搜索时扫描被控制的公司都是直接for循环，为什么不用考虑第一遍扫描时不能控制，但在后面能控制的公司的股份的支持下又能控制了的公司？？？

回答：考虑了，所以要多次执行循环，直到找不出任何新的控制关系的公司组为止。 ——mxalbert1996

[编辑] 另解

遇到i可以控制j，就将i,j入队，然后跟着队列，将被控者的股份贡献给控制者,能控制新的就将他们入队，一直操作下去。（弱弱的觉得只要更新一次股份就入队就行了吧？ byLynk）代码见Pascal中的第二个（MZD）其实类似于SPFA（旁注）

为了避免重复计算stock，可以先用一个数组inputState[][]存储输入的数据。然后再建两个数组：long conState[][]和bool owns[][] 然后循环不断更新owns和重建conState，直到owns不再变化。为了保证不重复计算，更新conState时只从inputState更新。具体做法如下：

const long comLimit=101;
for (long i=1;i<comLimit;i++) owns[i][i]=true;
bool changed=true;
//work
while (changed)
{
      changed=false;
      memset (conState,0,sizeof(conState));
      //根据owns从inputState重建conState  
      for (long i=1;i<comLimit;i++)
          for (long j=1;j<comLimit;j++)
              if (owns[i][j])
              {
                 for (long j2=1;j2<comLimit;j2++)
                     //conState[i][j]=x/inputState[i][j]=x  means i owns x% stocks of j
                     conState[i][j2]+=inputState[j][j2];        
              }
      //根据conState更新owns
      for (long i=1;i<comLimit;i++)
          for (long j=1;j<comLimit;j++)
              if (conState[i][j]>50 && owns[i][j]==false)
              {
                 changed=true;
                 owns[i][j]=true;
              }
}

Dijstra,好像很快就AC了,不知算法是否正确

uses math;
 
const
	MAXN = 100;
 
type
	arrn = array[1..MAXN] of longint;
 
var
	M,i,N,x,y,p,node,j : longint;
	hash : array[1..MAXN] of boolean;
	dist : arrn;
	map : array[1..MAXN] of arrn;
 
begin
	assign(input,'concom.in'); reset(input);
	assign(output,'concom.out'); rewrite(output);
	readln(M);
	for i := 1 to M do begin
		readln(x,y,p); map[x,y] := p;
		N := max(N,x); N := max(N,y);
	end;
	for node := 1 to N do begin
		fillchar(hash,MAXN,0); hash[node] := true;
		dist := map[node];
		repeat
			for i := 1 to N do
				if not hash[i] and (dist[i] > 50) then break;
			if hash[i] or (dist[i] <= 50) then begin
				for i := 1 to node-1 do
					if hash[i] then writeln(node,' ',i);
				for i := node+1 to N do
					if hash[i] then writeln(node,' ',i);
				break;
			end;
			hash[i] := true;
			for j := 1 to N do inc(dist[j],map[i,j]);
		until false;
	end;
	close(input); close(output);
end.

详见C++源码里面的第三个：

/*
ID:GeorgeG1
PROB:concom
LANG:C++
*/

yc5-yc:四重循环枚举AC！

难道数据没问题？ 11 11 51 这算什么？

[编辑] 参考代码

此题用宽搜要不断更新（update）就用宽搜用floyd 只能是 rp高才能过！！！！！表！！

USACO/concom

[编辑] 分析

[编辑] 另解

[编辑] 参考代码

查看

个人工具

导航

搜索

工具箱