uva 10746 - Crime Wave – The Sequel

Problem G

Crime Wave – The Sequel

Input: Standard Input

Output: Standard Output

Time Limit: 2 Seconds

n banks have been robbed this fine day. m (greater than or equal to n) police cruisers are on duty at various locations in the city. n of the cruisers should be dispatched, one to each of the banks, so as to minimize the average time of arrival at the nbanks.

Input

The input file contains several sets of inputs. The description of each set is given below:

The first line of input contains 0 < n <= m <= 20. n lines follow, each containing m positive real numbers: the travel time for cruiser m to reach bank n.

Input is terminated by a case where m=n=0. This case should not be processed.  

Output

For each set of input output a single number: the minimum average travel time, accurate to 2 fractional digits.

Sample Input                             Output for Sample Input

3 4 10.0 23.0 30.0 40.0 5.0 20.0 10.0 60.0 18.0 20.0 20.0 30.0 0 0

13.33

---

Problemsetter: Gordon Cormack, EPS

二分圖最大匹配轉最小費用流 - 加上源點與匯點
注意浮點數誤差，加上epsilon(1e-8)以保證四捨五入

#include<stdio.h>
#include<cstring>
#include<queue>
#include<cmath>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
#define INF (1e30)
#define MAXN 50
#define MAXM 900
#define eps 1e-8
using namespace std;

int N,M,D,K,LD,cases=1,e=0;
int head[MAXM],v[MAXM],next[MAXM],cap[MAXM],
    cnt[MAXN],flow[MAXN],p[MAXN],pe[MAXN];
double RES,dis[MAXN],cost[MAXM];
bool trav[MAXN];

void addedge(int a,int b,int K,double w){
    if(DBG)printf("addedge(%d): %d %d\n",e,a,b);
    v[e]=b,cap[e]=K,cost[e]=w,
    next[e]=head[a],head[a]=e++;
    v[e]=a,cap[e]=0,cost[e]=-w,
    next[e]=head[b],head[b]=e++;
}
bool relax(int u,int v,int e){
    if(DBG)printf("enter relax(%d) u v cap cost dis[v] %d %d %d %f %f\n",e,u,v,cap[e],cost[e],dis[v]);
    if(cap[e]&&dis[u]+cost[e]<dis[v]){
        flow[v]=min(flow[u],cap[e]);
        dis[v]=dis[u]+cost[e];
        p[v]=u,pe[v]=e;
        if(DBG)printf("  relax(%d): v cap dis %d %d %f\n",e,v,cap[v],dis[v]);
        return 1;
    }
    return 0;
}
void SPFA(int s,int t){
    int i,b,c,d,f;
    double w;
    queue<int>q;
    rep(i,M+N+2)dis[i]=INF;
    memset(trav,0,sizeof(trav));
    memset(flow,0,sizeof(flow));
    flow[0]=LD,dis[0]=0;
    q.push(0);
    while(q.size()){
        c=q.front(),w=dis[c];q.pop();
        if(DBG)printf("spfa v flow dis %d %d %f\n",c,flow[c],dis[c]);
        trav[c]=0;
        for(i=head[c];i!=-1;i=next[i]){
            b=v[i];
            if(relax(c,b,i)&&!trav[b]){
                if(DBG)printf("b %d F %d\n",b,cap[i]);
                trav[b]=1;
                q.push(b);
            }
        }
    }
    f=flow[t];
    LD-=f,RES+=f*dis[t];
    if(DBG)printf("final LD cost dis: %d %d %f\n",LD,f,dis[t]);
    for(b=t;b!=s;b=p[b]){if(DBG)printf("cut %d\n",pe[b]);cap[pe[b]]-=f,cap[pe[b]^1]+=f;}
}
void edmond(int s,int t){
    while(LD){
        if(DBG)printf("edm\n");
        SPFA(s,t);
    }
    if(DBG)printf("dist: %d\n",RES);
}
void ans(){
    RES=0,LD=N;
    edmond(0,N+M+1);
    printf("%.2f\n",RES/N+eps);
}
int main(){
    int a,b,cases=1;
    double c;
    while(scanf("%d%d",&N,&M)==2){
        if(N==0&&M==0)break;
        if(DBG)printf("N M %d %d\n",N,M);
        memset(head, -1, sizeof(head)),e=0;
        rep(i,N){
            rep(j,M)scanf("%lf",&c),addedge(j+1,i+M+1,1,c);
        }
        rep(i,N)addedge(i+M+1,N+M+1,1,0);
        rep(i,M)addedge(0,i+1,1,0);
        if(DBG)printf("cases %d\n",cases++);
        ans();
    }
}

uva 11396 - Claw Decomposition

Problem B
Claw Decomposition

Input: Standard Input

Output: Standard Output

A claw is defined as a pointed curved nail on the end of each toe in birds, some reptiles, and some mammals. However, if you are a graph theory enthusiast, you may understand the following special class of graph as shown in the following figure by the word claw.

If you are more concerned about graph theory terminology, you may want to define claw as K_1,3.

Let’s leave the definition for the moment & come to the problem. You are given a simple undirected graph in which every vertex has degree 3. You are to figure out whether the graph can be decomposed into claws or not.

Just for the sake of clarity, a decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list.

Input

There will be several cases in the input file. Each case starts with the number of vertices in the graph, V (4<=V<=300). This is followed by a list of edges. Every line in the list has two integers, a & b, the endpoints of an edge (1<=a,b<=V). The edge list ends with a line with a pair of 0. The end of input is denoted by a case with V=0. This case should not be processed.

Output

For every case in the input, print YES if the graph can be decomposed into claws & NO otherwise.

Sample Input                                                  Output for Sample Input

4 1 2 1 3 1 4 2 3 2 4 3 4 0 0 6 1 2 1 3 1 6 2 3 2 5 3 4 4 5 4 6 5 6 0 0 0

NO NO

---

Problemsetter: Mohammad Mahmudur Rahman

Special Thanks to: Manzurur Rahman Khan

Graph, Bipartite checking

<br/>#include&lt;stdio.h&gt;<br/>#include&lt;cstring&gt;<br/>#include&lt;string&gt;<br/>#include&lt;vector&gt;<br/>#define REP(i, b, n) for (int i = b; i &lt; n; i++)<br/>#define rep(i,n) REP(i, 0, n)<br/>#define DBG 0<br/>using namespace std;<br/><br/>int N,color[300];<br/>vector&lt;int&gt;egs[300];<br/>bool trav[300];<br/>bool mark(int u,int cr){<br/>    int b;<br/>    if(DBG)printf(&quot;mark %d %d\n&quot;,u,cr);<br/>    trav[u]=1,color[u]=cr;<br/>    int nc=(cr==1?2:1);<br/>    rep(i,egs[u].size()){<br/>        b=egs[u][i];<br/>        if(color[b]&amp;&amp;color[b]!=nc)return 0;         //traverse and wrong color<br/>        if(!trav[b])mark(b,nc);<br/>    }<br/>    return 1;<br/>}<br/>void ans(){<br/>    bool fail=0;<br/>    memset(color,0,sizeof(color));<br/>    memset(trav,0,sizeof(trav));<br/>    rep(i,N){<br/>        if(!trav[i]){<br/>            if(!mark(i,1)){fail=1;break;}<br/>        }<br/>    }<br/>    if(!fail)printf(&quot;YES\n&quot;);<br/>    else printf(&quot;NO\n&quot;);<br/>}<br/>int main(){<br/>    int a,b;<br/>    while(scanf(&quot;%d&quot;,&amp;N)==1){<br/>        rep(i,300)egs[i].clear();<br/>        if(N==0)break;<br/>        while(scanf(&quot;%d%d&quot;,&amp;a,&amp;b)==2){<br/>            if(a+b==0)break;<br/>            else a--,b--,egs[a].push_back(b),egs[b].push_back(a);<br/>        }<br/>        ans();<br/>    }<br/>}<br/>

11080 - Place the Guards

Problem G

Place the Guards
Input: Standard Input

Output: Standard Output

In the country of Ajabdesh there are some streets and junctions. Each street connects 2 junctions. The king of Ajabdesh wants to place some guards in some junctions so that all the junctions and streets can be guarded by them. A guard in a junction can guard all the junctions and streets adjacent to it. But the guards themselves are not gentle. If a street is guarded by multiple guards then they start fighting. So the king does not want the scenario where a street may be guarded by two guards. Given the information about the streets and junctions of Ajabdesh, help the king to find the minimum number of guards needed to guard all the junctions and streets of his country.

           

Input:

The first line of the input contains a single integer T (T<80 2="2" begins="begins" case="case" cases.="cases." class="GramE" each="each" indicating="indicating" nbsp="nbsp" number="number" of="of" span="span" test="test" the="the" with="with">integers

 v (1 ≤ v ≤ 200) and e (0 ≤ e ≤ 10000.). v is the number of junctions and e is the number of streets. Each of the next e line contains 2 integer f and t denoting that there is a street between f and t. All the junctions are numbered from 0 to v-1.

Output:

For each test case output in a single line an integer m denoting the minimum number of guards needed to guard all the junctions and streets. Set the value of m as -1 if it is impossible to place the guards without fighting.

Sample Input                             Output for Sample Input

2 4 2 0 1 2 3 5 5 0 1 1 2 2 3 0 4 3 4

2 -1

---

Problemsetter: Abdullah-al-Mahmud

Special Thanks: Md. Kamruzzaman

Graph, Bipartite checking

#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
#include<vector>
#define REP(i, b, n) for (int i = b; i < n; i++)
#define rep(i,n) REP(i, 0, n)
#define DBG 0
using namespace std;

int N,E,color[200],cn;
vector<int>egs[200];
bool trav[200];
bool mark(int u,int cr,int &len){
    int b;
    if(DBG)printf("mark %d %d\n",u,cr);
    trav[u]=1,color[u]=cr;
    if(cr==1)cn++;
    int nc=(cr==1?2:1);
    rep(i,egs[u].size()){
        b=egs[u][i];
        if(color[b]&&color[b]!=nc)return 0;         //traverse and wrong color
        if(!trav[b])len++,mark(b,nc,len);             
    }
    return 1;
}
void ans(){
    int tot=0,len,c;
    bool fail=0;
    memset(color,0,sizeof(color));
    memset(trav,0,sizeof(trav));
    rep(i,N){
        if(!trav[i]){
            cn=0,len=1;
            if(mark(i,1,len)){
                if(DBG)printf("len cn %d %d\n",len,cn);
                c=min(cn,len-cn);
                if(c==0)c=1;
                tot+=c;
            }
            else {fail=1;break;}
        }
    }
    if(!fail)printf("%d\n",tot);
    else printf("-1\n");
}
int main(){
    int n,m,a,b;
    scanf("%d",&n);
    rep(i,n){
        rep(i,200)egs[i].clear();
        E=0;
        scanf("%d%d",&N,&m);
        rep(i,m)scanf("%d%d",&a,&b),egs[a].push_back(b),egs[b].push_back(a),E++;
        ans();
    }
}